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_1$ $r_2$ $1 \le r_1 \lt r_2$ $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^{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(k)$ $f(x) \in \Theta(x)$ $n^{1-\epsilon}$

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

cc.complexity-theory nondeterminism time-hierarchy

— András Salamon
źródło

to miłe pytanie, András

— Suresh Venkat

Stephen Cook zaproponował programowanie liniowe jako możliwy separator dla

k = 2

$k=2$

— András Salamon,

Czy mógłbyś wyjaśnić, co rozumiesz przez „niekonstruktywny argument”? Dowód wykorzystujący przekątną nie musi być niekonstruktywny.

— Kaveh

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 , wtedy rzeczywiście okazały . $\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 . 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 . Możesz egzystencjalnie odgadnąć izolowane przypisanie, a następnie uniwersalnie zweryfikować (dla wszystkich $\Sigma_2 TIME[n]$ $k$ sposoby na podbicie dobitó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 czasu dla wszystkich . Jeśli , to jest w dla jakiegoś stałego (dowód używa efektywnej wersji twierdzenia Cooka: jeśli istnieje algorytm SAT działający w czasie $k$ $\Omega(n^k)$ $k$ $P=NP$ $\Sigma_2 TIME[n]$ $TIME[n^c]$ $c$ $n^d$ , wystarczy dowolne ). Ale udowodniliśmy, że w jest język, który nie występuje w dla każdego . Jest to sprzeczne, tak . $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 bitowe wystąpienia zostają zredukowane do wzoru IZOLOWANEGO SAT co najwyżej rozmiar) następnie $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$

— Ryan Williams
źródło

Dziękujemy za zgrabny argument pokazujący, że K-ISOLATED SAT nie wykona zadania.

— András Salamon,