Czy istnieją naturalne separacje w niedeterministycznej hierarchii czasu?

Oryginalne twierdzenie o niedeterministycznej hierarchii czasu wynika z Cooka (link do S. Cooka, Hierarchia niedeterministycznej złożoności czasu , JCSS 7 343–353, 1973). Twierdzenie to stwierdza, że ​​dla dowolnych liczb rzeczywistych i , jeśli wówczas NTIME ( ) jest ściśle zawarty w NTIME ( ).r 2 1 ≤ r 1 < $r_1$$r_2$$1 \le r_1 \lt r_2$ n r $n^{r_1}$$n^{r_2}$

Jedna kluczowa część dowodu wykorzystuje (nieokreśloną) diagonalizację do budowy języka oddzielającego od elementów mniejszej klasy. Jest to nie tylko niekonstruktywny argument, ale języki uzyskiwane w wyniku diagonalizacji zwykle nie dostarczają innych informacji niż sam podział.

Jeśli chcemy zrozumieć strukturę hierarchii NTIME, prawdopodobnie należy odpowiedzieć na następujące pytanie:

Czy istnieje język naturalny w NTIME ( ), ale nie w NTIME ( )? n $n^{k+1}$$n^k$

Jednym z kandydatów może być K-IZOLOWANY SAT , który wymaga znalezienia rozwiązania dla formuły CNF bez innych rozwiązań w odległości Hamminga k. Jednak udowodnienie, że dolna granica wydaje się trudne, jak zwykle. Oczywiste jest, że sprawdzenie k-kulki Hamminga jest wolne od potencjalnych rozwiązań „powinno” wymagać sprawdzenia przez różnych zadań, ale nie jest to łatwe do udowodnienia . (Uwaga: Ryan Williams wskazuje, że ta dolna granica dla -IZOLOWANEGO SAT faktycznie udowodniłaby P ≠ NP, więc ten problem nie wydaje się być właściwym kandydatem.)$\Omega(n^k)$$k$

Zauważ, że twierdzenie to obowiązuje bezwarunkowo, niezależnie od niesprawdzonych podziałów, takich jak P vs. NP. Odpowiedź twierdząca na to pytanie nie rozwiąże zatem P w porównaniu z NP, chyba że ma dodatkowe właściwości, takie jak IZOLOWANA SAT powyżej. $k$ Naturalne oddzielenie NTIME może być może pomóc w oświetleniu części „trudnego” zachowania NP, tej części, która bierze trudność z nieskończoną rosnącą sekwencją twardości.

Ponieważ dolne granice są trudne, przyjmuję jako odpowiedź języki naturalne, dla których możemy mieć dobry powód, by wierzyć w dolną granicę, chociaż może nie być jeszcze dowodu. Na przykład, jeśli to pytanie dotyczyło DTIME, to zaakceptowałbym -CLIQUE, dla nie zmniejszającej się funkcji , jako język naturalny, który prawdopodobnie zapewnia wymagane separacje, oparte na dolnych granicach obwodu Razborova i Rossmana oraz aproksymacji CLIQUE .f ( x ) ∈ Θ ( x ) n 1 - $f(k)$$f(x) \in \Theta(x)$$n^{1-\epsilon}$

(Edytowane w celu uwzględnienia komentarza Kaveha i odpowiedzi Ryana.)

O ile mi wiadomo, nie znamy takich języków, a jeśli tak, to istnieje znaczna kontrowersja na temat ich „naturalności”. Wiem, że to nie jest satysfakcjonująca odpowiedź, ale mogę powiedzieć:

(a) W przypadku udowodnienia czas dolna granica dla k izolowane SAT dla każdego k , wtedy rzeczywiście okazały P ≠ N P .$\Omega(n^k)$$k$$P \neq NP$

(b) Jednym ze sposobów, w jaki możesz wykazać, że K-IZOLOWANY SAT jest jednym z tych naturalnych problemów w jest wykazanie, że k-IZOLOWANY Problem SAT jest trudny (w zwykłym formalnym sensie posiadania skutecznych redukcji) dla N T I M E [ n k ] . W rzeczywistości jest to jedyny sposób, w jaki wiemy, jak udowodnić takie wyniki. Ale K-IZOLOWANY SAT prawdopodobnie nie jest trudny w tym sensie, istnieje kilka bardzo mało prawdopodobnych konsekwencji.$NTIME[n^{k+1}] - NTIME[n^k]$$NTIME[n^k]$

Głównym powodem jest to, że instancje K-IZOLOWANE SAT są rozwiązywalne w , niezależnie od k . Możesz egzystencjalnie odgadnąć izolowane przypisanie, a następnie uniwersalnie zweryfikować (dla wszystkich O ( log ( ∑ k i = 1 ($\Sigma_2 TIME[n]$$k$sposoby na podbicie dokbitów w zadaniu), że żadne z innych „lokalnych” zadań nie działa.$O(\log (\sum_{i=1}^k {n \choose i}))$$k$

Oto dowód części (a). Niech ISOLATED SAT będzie wersją problemu z podaną jako część danych wejściowych (powiedzmy unary). Załóżmy, że udowodnimy, że ISOLATED SAT wymaga Ω ( n k ) czasu dla wszystkich k . Jeśli P = N P , to Σ 2 T I M E [ n ] jest w T I M E [ n c ] dla jakiegoś stałego c (dowód używa efektywnej wersji twierdzenia Cooka: jeśli istnieje algorytm SAT działający w czasie n $k$$\Omega(n^k)$$k$$P=NP$$\Sigma_2 TIME[n]$$TIME[n^c]$$c$$n^d$, wystarczy dowolne ). Ale udowodniliśmy, że w Σ 2 T I M E [ n ] jest język, który nie występuje w T I M E [ n k ] dla każdego k . Jest to sprzeczne, tak P ≠ N P .$c > d^2$$\Sigma_2 TIME[n]$$TIME[n^k]$$k$$P \neq NP$

Oto dowód części (b). Jeśli każdy może być skutecznie zredukowany do wzoru k-IZOLOWANEGO SAT (np. Wszystkie n bitowe wystąpienia L zostają zredukowane do wzoru k- IZOLOWANEGO SAT co najwyżej f ( k ) n c rozmiar) następnie N P = ⋃ k N T I M E [ n k ] ⊆ Σ 2 T I M E $L \in NTIME[n^k]$$n$$L$$k$$f(k) n^{c}$$NP=\bigcup_{k} NTIME[n^k] \subseteq \Sigma_2 TIME[n^{c+1}]$$coNP \neq NP$$NP$