Teoretyczne informatyka

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

1
Wyraźne separacje między obwodami kwantowymi o głębokości poli- i logarytmicznej
Następujący problem pojawia się na liście Aaronsona Dziesięć pół-wielkich wyzwań dla teorii obliczeń kwantowych . Jest B Q P = B P PB Q N CbQP.=bP.P.bQN.do\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} Innymi słowy, i „kwantową” część dowolnego algorytmu kwantowej być skompresowane do p o l y l o g (n)polylosol(n)\mathrm{polylog}(n) głębokości, pod warunkiem, że jesteśmy …
3
Czy możemy udowodnić słabą normalizację dla Systemu F poprzez indukcję na transfinite porządkowej
Słabą normalizację dla prostego rachunku lambda o typie można udowodnić (Turinga) przez indukcję na . Rozszerzony rachunek lambda z rekursorami na liczbach naturalnych (Gentzen) ma słabą strategię normalizacji przez indukcję na ϵ 0 .ω2ω2\omega^2ϵ0ϵ0\epsilon_0 Co z systemem F (lub słabszym)? Czy w tym stylu jest słaby dowód normalizacji? Jeśli nie, …
2
Twarde instancje do testowania izomorfizmu grafów
Czy przypadek bardzo regularnych grafów jest najtrudniejszy do testowania GI? gdzie „najtrudniejszy” jest używany w pewnym sensie „zdrowego rozsądku” lub „średnio”, że tak powiem. Wolfram MathWorld wspomina o niektórych „patologicznie trudnych grafach”. Czym oni są? Mój przykładowy zestaw 25 par wykresów: http://funkybee.narod.ru/graphs.htm Testowałem wiele innych, ale wszystkie tego samego rodzaju …
1
Problemy z logDCFL-complete
LogCFL to zestaw wszystkich języków, które można sprowadzać do przestrzeni logicznej do języka bezkontekstowego. Podobnie LogDCFL jest zbiorem wszystkich języków, które są przestrzenią logiczną redukowalną do deterministycznego języka bezkontekstowego. Zobacz ten artykuł na Wikipedii, aby zapoznać się z niektórymi naturalnymi problemami związanymi z logCFL. Istnieje kilka innych interesujących problemów z …
1
Odczyt na
Co powinienem przeczytać, aby zrozumieć ten problem? B Q P= B PP.B Q NdobQP.=bP.P.bQN.doBQP = BPP^{BQNC}B Q PbQP.BQPB P.P.B Q NdobP.P.bQN.doBPP^{BQNC}, ale pytanie brzmi, czy istnieje jakaś konkretna funkcja „inicjująca” taką wyrocznię. - Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html
6
Kiedy znaleźliśmy lepsze granice dla znanych algorytmów?
Czy istnieją interesujące przypadki algorytmów, które zostały opublikowane ze sprawdzonymi granicami i gdzie opublikowano później ściśle lepsze ograniczenia? Nie lepsze algorytmy z lepszymi granicami - oczywiście tak się stało! Ale lepsza analiza prowadząca do lepszego powiązania z istniejącym algorytmem Myślałem, że mnożenie macierzy jest tego przykładem, ale sam sobie z …
1
Podziel wykres na cykle rozłączne węzłów
Powiązany problem: Twierdzenie Veblena stwierdza, że ​​„Wykres dopuszcza rozkład cyklu wtedy i tylko wtedy, gdy jest on parzysty”. Cykle są rozłączne na krawędziach, ale niekoniecznie są rozłączne w węzłach. Innymi słowy: „Zestaw krawędzi wykresu można podzielić na cykle, jeśli i tylko wtedy, gdy każdy wierzchołek ma równy stopień”. Mój problem: …
1
Bariery, aby pokazać
Wszyscy wiemy, że pokazanie ma bariery. Wszyscy badaliśmy te bariery, ponieważ uważamy, że P ≠ N P.P≠NPP≠NPP\ne NPP≠NPP≠NPP\ne NP . Załóżmy jednak, że i są mądrzy ludzie, którzy wierzą, że taka możliwość istnieje . Jeśli tak rzeczywiście jest, to sam fakt, że nie widzieliśmy żadnych dobrych algorytmów, wskazuje, że mogą …
15 p-vs-np  barriers 
1
Czy ?
Oczekuję, że odpowiedź brzmi „nie”, ale tak naprawdę nie mogłem skonstruować kontrprzykładu. Różnica polega na tym, że w ∩ ε > 0 D T I M E ( O ( n 2 + ε ) )∩ε>0DTIME(O(n2+ε))∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) możemy nie być w stanie wybrać algorytmu O ( n 2 + ε …
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.