TMs e oráculos delimitados pelo espaço

20

Em geral, a fita de consulta de um oráculo conta para a complexidade espacial de uma TM. No entanto, parece plausível permitir uma fita oracle somente para gravação (como é usada nas reduções de espaço L).

Essa construção é útil? Isso produz resultados particularmente absurdos?

cc.complexity-theory space-bounded oracles Jeremy Hurwitz
fonte

Se você possui uma TM com uma fita Oracle somente para gravação, como lê a resposta? Você pode simplesmente esquecer o oráculo então.

Marcos Villagra

1

Existem questões delicadas ao decidir qual é a definição correta de acesso ao oráculo para máquinas com limite de espaço. Veja "Relativizando pequenas classes de complexidade e suas teorias" de Klaus Aehlig, Stephen Cook e Phuong Nguyen, CSL 2007.

Kaveh

@Marcos: acredito que a resposta é simplesmente o estado interno resultante da máquina e não está gravado na fita oracle.

Joe Fitzsimons

Qual é a referência para esta definição de máquinas oracle com espaço limitado?

Miforbes

10

Penso que um fato surpreendente é que, neste modelo, o teorema de Savitch "obviamente" não se relativiza. Ou seja, pode-se ver que e neste modelo, e atualmente não temos sabe que $PSPACE^P=EXPTIME$ $NPSPACE^P=NEXPTIME$ (e o teorema de Savitch, neste contexto, não parece dar). Eu estaria interessado em saber se isso pode ser empurrado para "provadamente" não relativizar. $EXPTIME=NEXPTIME$

Pode-se observar também que neste modelo. $NL^{NL}=NL^L=NP$

No entanto, acho que vale a pena pensar nesse modelo, no que diz respeito a questões de relativização no teorema da hierarquia espacial. Além disso, em algum sentido, eu quero fazer consultas poli-dimensionados para . $L^A$ $A$

miforbes
fonte

1

Uma coisa que esqueci: como NL = coNL, devemos querer NL ^ NL = NL, mas claramente se NL ^ NL = NP neste modelo, não podemos usar NL = coNL para recolher a "hierarquia da NL". Em uma noção diferente de oráculos delimitados pelo espaço, a hierarquia realmente entra em colapso (consulte o artigo NL = coNL de Immerman para obter referências).

Miforbes

Você possui uma referência ? I seria de esperar

. De fato, seja

uma linguagem recursivamente enumerável,

a TM que reconhece

e

a TM que lê uma entrada e um número

de "1" e depois simula

para esta entrada em

etapas. Então, sem usar nenhum espaço, eu poderia copiar a entrada na fita oracle, adivinhar o número de 1 necessário e consultar

.

N S P A C E (0)^{P} = R E

$\rm{NSPACE(0)^P=RE}$

L

$L$

M

$M$

L

$L$

M^{'}

$M'$

n

$n$

M

$M$

n

$n$

M^{'}

$M'$

Arthur MILCHIOR

9

Isso pode não responder à sua pergunta (que, para ser honesto, não entendo completamente), mas acho que está no mesmo espírito. Sabe-se que há uma diferença na redutibilidade entre um espaço de log TM com uma fita oracle e uma com acesso a várias fitas oracle. Além disso, a seguinte noção de espaço para log possui boas propriedades: a TM pode usar apenas uma quantidade de espaço em sua fita de trabalho, mas pode usar uma quantidade polinomial de espaço em suas fitas Oracle.

Referência: http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf

Aaron Sterling
fonte

3

NSPACE (0) P = RE, o que eu acho que é um pouco absurdo.

De fato, seja L uma linguagem recursivamente enumerável, M a TM que reconhece L e M ′ a TM que lê uma entrada e um número n de "1" e depois simula M para esta entrada em n etapas. Então, sem usar nenhum espaço, eu poderia copiar a entrada na fita oracle, adivinhar o número de 1 necessário e consultar M '.

Então, M 'aceitará se M aceitar e terá uma entrada grande o suficiente para ser polinomial.

Arthur MILCHIOR
fonte

TMs e oráculos delimitados pelo espaço

Respostas: