Czy istnieje jakiś znany problem NP-Complete (lub NP-Intermediate) w podliniowej niedeterministycznej przestrzeni?

Istnieje kilka problemów z NP-Complete ($\mathsf{SAT}$, $\mathsf{SUBSETSUM}$itd.) $\mathsf{DSPACE(n)}$. Co z przestrzeniami nieliniowymi?

Czy istnieje jakiś znany problem NP-Complete (lub NP-Intermediate) w podliniowej niedeterministycznej przestrzeni?

Należą do płaskiej wersji wielu problemów NP-zupełnych $NTISP(n,n^q)$ dla niektórych $q<1$

Zobacz na przykład „ Dolne granice i całkowite problemy w niedeterministycznych klasach liniowego czasu i sublinearnej złożoności przestrzeni ” P. Chapdelaine i E. Grandjean (2006)

Każdy problem ma taką wersję, po prostu ją PAD! Np. Język, który składa się z prawdziwej 3CNF o długości m, po której następuje m ^ 2 0, jest w DSPACE (sqrt (n)).

Dla dowolnego języka w $\mathsf{NP}$ istnieje dowód, który można zweryfikować za pomocą $O(\log n)$przestrzeń robocza. Trzeba tylko użyć tych samych pomysłów, które zostały wykorzystane do udowodnienia, że ​​SAT jest$\mathsf{NP}$-kompletny. Z definicji, biorąc pod uwagę$\mathsf{NP}$ język $L$wiemy, że istnieje maszyna Turinga $M$ tak, że dla każdego $x \in L$ istnieje $y$ takie, że $M(x, y)$akceptuje. Możemy zbudować weryfikowalny dowód przestrzeni logicznej$x$ pisząc $y$ i tableau obliczeń z $M$ na wejściu $x, y$. W przestrzeni logów łatwo jest zweryfikować, czy tableau opisuje prawidłowe obliczenia akceptujące$M$. Podobnie dla każdego$x \not \in L$ i jakikolwiek $y$, brak prawidłowego obliczenia $M(x, y)$ akceptuje, więc weryfikator obszaru logów nie zaakceptuje żadnego obrazu.

Oczywiście to nie pokazuje$\mathsf{NP} = \mathsf{NL}$ (ponieważ to by sugerowało $\mathsf{NP} = \mathsf{P}$). Powodem jest to, że weryfikator ma dwukierunkowy dostęp do dowodu (może przechodzić do przodu i do tyłu). Definicja weryfikatora$\mathsf{NL}$ daje weryfikatorowi przestrzeni logicznej tylko jednokierunkowy dostęp do dowodu (po odczytaniu odrobiny dowodu i ruchu głowy w prawo nie może się poruszać w lewo).