Existe algum problema NP-Completo (ou NP-Intermediário) no espaço sub-linear não-determinístico?

Existem alguns problemas de NP-Complete ( , , etc.) conhecidos por estarem em . E os espaços sub-lineares?S U B S E T S U $\mathsf{SAT}$$\mathsf{SUBSETSUM}$$\mathsf{DSPACE(n)}$

Existe algum problema NP-Completo (ou NP-Intermediário) no espaço sub-linear não-determinístico ?

A versão planar de muitos problemas completos de NP pertence ao para alguns$NTISP(n,n^q)$$q<1$

Veja, por exemplo, " Limites inferiores e problemas completos em classes de complexidade linear não-determinística de tempo e espaço sub-linear ", de P. Chapdelaine e E. Grandjean (2006)

Qualquer problema tem essa versão, apenas PAD it! Por exemplo, a linguagem que consiste em um 3CNF verdadeiro de comprimento m seguido por m ^ 2 0 está em DSPACE (sqrt (n)).

Para qualquer idioma em , existe uma prova que pode ser verificada usando espaço de trabalho . Basta usar as mesmas idéias usadas para provar que SAT é -completo. Por definição, dada a linguagem , sabemos que existe uma máquina de tortura tal que para qualquer exista um tal que aceite. Podemos construir uma prova verificável do espaço de log para escrevendo e o quadro de computação de na entrada$\mathsf{NP}$$O(\log n)$$\mathsf{NP}$$\mathsf{NP}$$L$$M$$x \in L$$y$$M(x, y)$$x$$y$$M$$x, y$. É fácil de verificar em logspace que o quadro descreve um cálculo aceitar válida de . Da mesma forma, para qualquer e qualquer , nenhum cálculo válido de aceita, portanto, o verificador do espaço de log não aceita nenhum quadro.$M$$x \not \in L$$y$$M(x, y)$

Obviamente, isso não mostra que (porque isso implicaria ). O motivo é que o verificador tem acesso bidirecional à prova (pode ir e voltar). A definição do verificador de prova de fornece ao verificador do espaço de log apenas um caminho para a prova (uma vez que um pouco da prova é lida e a cabeça se move para a direita, ela não pode se mover para a esquerda).N P = P N $\mathsf{NP} = \mathsf{NL}$$\mathsf{NP} = \mathsf{P}$$\mathsf{NL}$