Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

2
Co się stanie, jeśli poprawimy twierdzenia dotyczące hierarchii czasu?
f,gf,gf,gf(n)logf(n)=o(g(n))f(n)log⁡f(n)=o(g(n))f(n) \log f(n) = o(g(n))f , g f ( n + 1 ) = o ( g ( n ) )DTIME(f(n))⊊DTIME(g(n))DTIME(f(n))⊊DTIME(g(n)) DTIME(f(n)) \subsetneq DTIME(g(n))f,gf,gf,gf(n+1)=o(g(n))f(n+1)=o(g(n))f(n+1)=o(g(n))jest to NTIME(f(n))⊊NTIME(g(n)).NTIME(f(n))⊊NTIME(g(n)). NTIME(f(n)) \subsetneq NTIME(g(n)). Istnieje wiele (starych i aktualnych) wyników, które wykorzystują twierdzenia o hierarchii czasu do udowodnienia dolnych granic. Oto moje pytania: Co się …
1
Interaktywny dowód dla HORN-SAT?
Czy istnieje sposób, w jaki przysłowie może przekonać weryfikatora, że ​​niektóre wyrażenia HORN-SAT są zadowalające? Oczywiście może się to wydawać głupie, ponieważ istnieją algorytmy czasu liniowego dla HORN-SAT. Z drugiej strony HORN-SAT jest P-zupełny, co oznacza, że ​​nie ma algorytmów przestrzeni logów, chyba że P = L. W związku z …
1
Czy można zastosować opisową złożoną wersję twierdzenia Rice'a do oddzielenia AC0 i PSPACE?
W tym pytaniu wspomniano, że istnieją opisowe wersje złożoności twierdzenia Rice'a. Znalazłem dowód na następujące twierdzenie: Biorąc pod uwagę klasę złożoności C , nietrywialnych właściwości języków w C nie można obliczyć w C Wcześniej opublikowałem znaleziony dowód, ale ponieważ był on tak długi i ponieważ w komentarzach wskazano, że ten …
3
Dlaczego nie używamy większych klas do badania determinizmu kontra niedeterminizmu?
W poprzednim pytaniu dotyczącym hierarchii czasu dowiedziałem się, że równości między dwiema klasami mogą być propagowane do bardziej złożonych klas, a nierówności mogą być propagowane do mniej złożonych klas, z argumentami wykorzystującymi wypełnianie. Dlatego przychodzi mi na myśl pytanie. Dlaczego badamy pytanie dotyczące różnych rodzajów obliczeń (lub zasobów) w najmniejszej …
3
Praktyczne konsekwencje
tło Obwód złożoność C 0 jest zdefiniowany jako zbiór rodzin obwodu (tj sekwencje obwodów, po jednym dla każdej wielkości wejściowej) o ograniczonej głębokości i wielomianu wielkości zbudowany przy użyciu nieograniczona fan-in AND, OR i NOT.AC0ZAdo0AC^0 Funkcja parzystości z wejściem n- bitowym jest równa XOR bitów na wejściu.⊕⊕\oplusnnn Jednym z pierwszych …
1
Twierdzenie o bezpośredniej sumie dla złożoności przestrzeni klauzuli rozdzielczości?
Rozwiązanie to program mający na celu wykazanie niezadowalającej wartości CNF. Dowodem na rozwiązanie jest logiczne odjęcie pustej klauzuli dla klauzul początkowych w CNF. W szczególności każdy punkt początkowy można wywnioskować, i dwóch punktach ∨ x i B ∨ Kontakty x klauzula ∨ B można wywnioskować, jak również. Odrzucenie jest sekwencją …
1
Jednolita hierarchia problemów obejmujących złożoność i hierarchie obliczeniowe
Czy ktoś zna zestaw problemów, które różnią się równomiernie i obejmują jedną z „interesujących” hierarchii złożoności i obliczalności? Przez interesujące rozumiem na przykład Hierarchię Wielomianową, Hierarchię Arytmetyczną lub Hierarchię Analityczną. A może (N) P, (N) EXP, 2 (N) EXP, ……\ldots 0 , 0′, 0′¯¯¯¯, 0′ ′, 0′ ′¯¯¯¯¯, …0,0′,0′¯,0″,0″¯,…0, 0', …
1
Skończona jednokierunkowa permutacja z nieskończoną domeną
Niech będzie permutacją. Zauważ, że chociaż działa w nieskończonej domenie, jego opis może być skończony. Przez opis rozumiem program, który opisuje funkcjonalność . (Jak w złożoności Kołmogorowa.) Zobacz wyjaśnienia poniżej. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon \{0,1\}^* \to \{0,1\}^*ππ\piππ\pi Na przykład funkcja NOT jest jedną z takich permutacji: funkcja NOT (x) Niech y …
2
Złożoność ukrytej łamigłówki wielokątów na kwadratowych siatkach?
Hiroimono jest popularną łamigłówką . Interesuje mnie złożoność obliczeniowa powiązanej układanki.N.P.NPNP Problemem jest: Dane wejściowe : Biorąc pod uwagę zestaw punktów na siatce kwadratowej x i liczbie całkowitejn knnnnnnkkk Pytanie : Czy istnieje wielokąt prostoliniowy (jego boki równoległe do osi lub ) taki, że liczba punktów na rogach wielokąta wynosi …
2
Przybliżanie nietrywialnego automorfizmu grafów?
Wykres automorfizmem jest permutacją węzłów wykres indukuje bijection na zestawie krawędź EEE . Formalnie jest to permutacja fff węzłów takich jak (u,v)∈E(u,v)∈E(u,v)\in E iff (f(u),f(v))∈E(f(u),f(v))∈E(f(u),f(v))\in E Zdefiniuj naruszoną krawędź dla pewnej permutacji jako krawędź odwzorowana na inną niż krawędź lub krawędź, której preimage nie jest krawędzią. Dane wejściowe : niesztywny …
1
CSP z nieograniczoną ułamkową szerokością hipertree
za´za´\acute{\rm a}H ∈ P T I M EH.H.HH.H.H∈ P.T.jaM.mi∈P.T.jaM.mi\in PTIME Definicje itp. Świetny przegląd standardowych rozkładów drzew i ich szerokości znajduje się tutaj (Dziękujemy z góry, JeffE!). Niech H.H.H będzie hipergrafatem. Następnie dla hipergraph H.H.H i mapowania γ: E( H) → [ 0 , ∞ )γ:mi(H.)→[0,∞)\gamma : E(H) \rightarrow [0,\infty) …
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.