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

9

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 MSATSUBSETSUMDSPACE(n)

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

Abuzer Yakaryilmaz
fonte

Respostas:

14

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)).

domotorp
fonte
Obrigado! Você tem alguma idéia sobre o espaço poli-logarítmico?
Abuzer Yakaryilmaz
11
basta preencher um 3CNF com zeros? 2n
Sasho Nikolov
2
@ Sasho: Então o problema deixaria de ser NP-completo, você só pode PAD com um número poli de zeros.
Domotorp
11
@ Abuzer: Eu acho que o espaço poly-log implicaria que o NP faz parte do DTIME [ ]. Isso é aberto e improvável. 2polylog
Domotorp
@domotorp: Sim, você está certo! Obrigado!
Abuzer Yakaryilmaz
11

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 entradaNPO(logn)NPNPLMxLyM(x,y)xyMx,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.MxLyM(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 LNP=NLNP=PNL

Sasho Nikolov
fonte
Eu não entendi a ideia! Você quer dizer verificação probabilística? Nesse caso, o espaço constante é suficiente para qualquer idioma no NP desde o . Ou você quer dizer redução do espaço de log de qualquer idioma no NP para o SAT? Estou realmente confuso! DSPACE(2n)IP(1)
Abuzer Yakaryilmaz
11
Deixe-me tentar de outra maneira: uma maneira padrão de definir é como a classe de linguagens que possuem verificadores políticos determinísticos. Estou dizendo que uma definição equivalente é definir como a classe de idiomas que possuem verificadores determinísticos de espaço de log com acesso de leitura múltipla à prova. nenhuma aleatoriedade é necessária. NPNP
Sasho Nikolov 5/05
4
Obrigado. Na verdade, eu sabia disso :) A classe não determinística do espaço de log com base em sua explicação é indicada como e sim, . Além disso, . As noções "off-line" e "on-line", como você apontou, representam os tipos de acesso à prova fornecida. REF: Seção 5.3.1 da Complexidade Computacional por Oded Goldreich (2008). N P = N S P A C E o f f - l i n e ( l o g ) N L = N S P A C E o n - l i n e ( l o gNSPACEoff-line(log)NP=NSPACEoff-line(log)NL=NSPACEon-line(log)
Abuzer Yakaryilmaz