Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Czy niemożność obliczenia złożoności Kołmogorowa wynika z twierdzenia Lawpowa o punkcie stałym?
Wiele twierdzeń i „paradoksów” - przekątna Cantora, nierozstrzygalność nienawiści, nierozstrzygalność złożoności Kołmogorowa, niekompletność Gödela, niekompletność Chaitina, paradoks Russella itp. - wszystkie mają w zasadzie ten sam dowód po przekątnej (zauważ, że jest to bardziej specyficzne niż to, że mogą wszystko to można udowodnić za pomocą diagonalizacji; wydaje się raczej, że …
1
Jak nie obliczyć najmniejszego okręgu zawierającego skończony zestaw kół
Załóżmy, że mamy skończony zbiór LLL dysków w R2R2\mathbb{R}^2 , i chcemy obliczyć najmniejszą dysku DDD , dla którego ⋃L⊆D⋃L⊆D\bigcup L\subseteq D . Standardowy sposób ten jest użycie algorytmu Matousek, Sharir i Welzl [1], aby znaleźć podstawę BBB z LLL i pozwolić D=⟨B⟩D=⟨B⟩D=\langle B\rangle najmniejsza dysku zawierającej ⋃B⋃B\bigcup B . …
2
Odniesienie do „bardziej algebraicznego” podejścia do automatów wypychających i świetlówek kompaktowych?
W książce Sakarovitcha na temat teorii automatów jest napisane we wstępie do części dotyczącej racjonalności w wolnej grupie, że przedstawiony w niej materiał stanowi „fundament prawdziwie matematycznej teorii języków bezkontekstowych”. Nie jest to jednak jednoznaczne, ponieważ języki bezkontekstowe i automaty wypychające są poza zakresem książki. Zdaję sobie sprawę z niektórych …
1
Jaka jest wyrocznia o minimalnej złożoności, która oddziela PSPACE od hierarchii wielomianowej?
tło Wiadomo, że istnieje oracle tak, że .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Wiadomo nawet, że separacja dotyczy przypadkowej wyroczni. Nieformalnie można to interpretować w ten sposób, że istnieje wiele wyroczni, dla których i są osobne.P HPSPACEPSPACEPSPACEPHPHPH Pytanie Jak skomplikowane są te wyrocznie, …
1
Porada dla matematyka próbującego przedstawić artykuł na konferencji CS?
Jestem matematykiem, który pracuje przede wszystkim w spektralnej teorii samozporządkowania i operatorów unitarnych. Niektóre z moich badań mają znaczenie podczas spacerów kwantowych, w szczególności mam jeden artykuł, który chciałbym przedstawić na konferencji Quantum Information Processing, która odbędzie się w styczniu w Seattle. Kultura teoretycznej społeczności CS wydaje się bardzo różna …
3
Jak często występuje przejście fazowe w problemach z NP-zupełnym?
Powszechnie wiadomo, że wiele problemów z kompletnym NP wykazuje przejście fazowe. Interesuje mnie przejście fazowe w odniesieniu do ograniczenia w języku, a nie twardości danych wejściowych w stosunku do algorytmu. Aby pojęcie było jednoznaczne, formalnie zdefiniujmy go w następujący sposób. Język wykazuje przejście fazowe (w odniesieniu do powstrzymywania), jeśliLLL Istnieje …
2
Najmniejszy możliwy uniwersalny kombinator
Szukam najmniejszego możliwego uniwersalnego kombinatora , mierzonego liczbą abstrakcji i aplikacji wymaganych do określenia takiego kombinatora w rachunku lambda . Przykłady uniwersalnych kombinatorów obejmują: rozmiar 23: λf.f (fS (KKKI)) K. rozmiar 18: λf.f (fS (KK)) K. rozmiar 14: λf.fKSK rozmiar 12: λf.fS (λxyz.x) rozmiar 11: λf.fSK gdzie S = λxyz.xz …
2
Złożoność problemu przecięcia cosetów
Biorąc pod uwagę grupę symetrii i dwie podgrupy i , czy ?SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset O ile mi wiadomo, problem ten znany jest jako problem przecięcia cosetów. Zastanawiam się, jaka jest złożoność? W szczególności, czy wiadomo, że ten problem występuje w CoAM? Co więcej, jeśli jest ograniczone do abelowego, …
1
Osiągalność DAG z przestrzenią O (n log n) i zapytaniami w czasie O (log n)?
Dla skierowanego acykliczny wykres , istnieje struktura danych zapytań, która pozwala na osiągalności bez konieczności kwadratowej przestrzeni lub czasu, liniowy? Idealnie szukam algorytmu wykorzystującego tylko przestrzeń O (log n) na wierzchołek i czas logarytmiczny,⟨ V, E⟩⟨V.,mi⟩{\langle}V,E{\rangle} gdzie .n = |V.| + |mi|n=|V.|+|mi|n=|V|+|E| Intuicyjnie wydawało mi się oczywiste, że taka struktura …
2
Minimalna skumulowana suma zestawu
Rozważ ten problem: biorąc pod uwagę listę zbiorów skończonych, znajdź porządek który minimalizuje .s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots Czy istnieją na to znane algorytmy? Jaka jest jego złożoność? Nie byłem jeszcze w stanie wymyślić wydajnego optymalnego algorytmu, ale nie …
2
Czy tradycyjna analiza filtrów Bloom jest nieprawidłowa?
Artykuł ten twierdzi, że tradycyjna analiza poziomu błędu w filtrach Blooma jest nieprawidłowa, a następnie przedstawia długą i niepraktyczną analizę rzeczywistego poziomu błędu. Powiązany artykuł został opublikowany w 2010 r., Ale widziałem, że tradycyjna analiza filtrów Blooma jest nadal nauczana w ramach różnych kursów algorytmów i struktur danych. Czy tradycyjna …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.