NTIME (n ^ k) ≠ DTIME (n ^ k)?

W „O determinizmie kontra niedeterminizm i pokrewnych problemach” (Proc. IEEE FOCS, strony 429–438, 1983) Paul, Pippenger, Szemerédi i Trotter udowodnili, że .
$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$

Odpowiada to na moje pytanie przy k = 1. Czy coś wiadomo o podobnym wyniku dla innego ustalonego k?

Żadna bezwarunkowa dolna granica nie jest znana dla żadnego w modelu multitape TM (ani żadnego modelu mocniejszego).$k \geq 2$

Ravi Kannan badał ten problem w „Ku oddzieleniu niedeterminizmu od determinizmu” (1984) . Próbując pokazać udało mu się udowodnić, że: istnieje jakaś uniwersalna stała taka, że ​​dla każdego , . Tutaj PRZESTRZEŃ CZASOWA (n ^ k, n ^ {k / c}) to klasa języków rozpoznawanych przez maszyny używające jednocześnie czasu n ^ k i spacji n ^ {k / c} . Oczywiście CZAS-PRZESTRZEŃ (n ^ k, n ^ {k / c}) \ subseteq CZAS (n ^ k), ale nie wiadomo, czy są one równe.N T I M E ( n k ) ≠ T I M E ( n k ) c ≥ 1 k N T I M E ( n k ) ⊈ T I M E - S P A C E ( n k , n k / c ) T I M E - S P A C $NTIME(n^k) \neq TIME(n^k)$$c \geq 1$$k$$NTIME(n^k) \not \subseteq TIME-SPACE(n^k,n^{k/c})$( n k , n k / c ) n k n k / c T I M E - S P A C E ( n k , n k / c ) ⊆ T I M E ( n k$TIME-SPACE(n^k, n^{k/c})$$n^k$$n^{k/c}$$TIME-SPACE(n^k,n^{k/c}) \subseteq TIME(n^k)$

Jeśli dla jakiegoś k \ geq 2 założysz,$k \geq 2$ że $NTIME(n^k) = TIME(n^k)$ , otrzymasz interesujące konsekwencje. $P=NP$ jest oczywiste, ale sugeruje również, że ${\sf NL} \neq {\sf P}$ . Można to udowodnić za pomocą argumentu „handel alternatywny”. Zasadniczo, dla każdego $k$ i każdego języka $L \in {\sf NL}$ istnieje stała $c$ i pewna przemienna maszyna, która rozpoznaje $L$ i dokonuje zmian $c$ , zgaduje $O(n)$ bitów na przemian, a następnie przełącza się w tryb deterministyczny i działa w czasie $n^k$ . (Wynika to na przykład z zabawy z konstrukcjami wFortnow, „Czasoprzestrzeń kompromisów dla satysfakcji” (1997) .) Teraz, jeśli $TIME(n^k) = NTIME(n^k)$ to wszystkie te $c$ alternacje można usunąć przy niewielkim obciążeniu, a ty skończysz z $TIME(n^k)$ obliczeń, które rozpoznaje $L$ . Stąd ${\sf NL }\subseteq TIME(n^k) \neq {\sf P}$ . Prawdopodobnie nie istnieje taka naprzemienna symulacja, ale jeśli możesz to wykluczyć, będziesz mieć dolną granicę, której szukasz. (Uwaga: uważam, że powyższy argument znajduje się również w pracy Kannana).

choć nie do końca to, o co pytasz, rj lipton komentuje na swoim blogu podstawową trudność wyników w tym obszarze oraz że typowe podejście do „paddingu” nie ma zastosowania [1] i zwraca uwagę, że cytowany niedawno wynik PPST został nieznacznie rozszerzony (przez czynnik logarytmiczny) o Santhanam [2] tj

[1] http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little/

[2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392