Qual é a verdadeira razão pela qual IP = PSPACE não é relativizante?

$O$ ${\sf coNP}^O \not\subseteq {\sf IP}^O$ ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ $O$

No entanto, vi poucas pessoas dando uma explicação "direta" para o motivo pelo qual o resultado não é relativizado, e a resposta usual é "aritmetização". Após a inspeção da prova de IP = PSPACE, essa resposta não é falsa , mas não é satisfatória para mim. Parece que a razão "real" remonta à prova de que o problema TQBF - fórmula booleana quantificada verdadeira - está completo para o PSPACE; para provar isso, é necessário mostrar que é possível codificar configurações de uma máquina PSPACE em um formato de tamanho polinomial e (esta parece ser a parte não relativizante), é possível codificar transições "corretas" entre configurações em um tamanho polinomial fórmula booleana - isso usa uma etapa no estilo Cook-Levin. ${\sf IP} = {\sf PSPACE}$

A intuição que eu desenvolvi é que os resultados não relativizantes são aqueles que remexem no âmago da questão das Máquinas de Turing, e a etapa em que o TQBF é mostrado completo para o PSPACE é o local em que essa cutucada acontece - e a etapa de aritmetização pode aconteceu apenas porque você tinha uma fórmula booleana explícita para aritmetizar.

Isso me parece ser a razão fundamental pela qual IP = PSPACE não é relativizante; e o mantra do folclore de que as técnicas de aritmetização não se relativizam parece ser um subproduto disso: a única maneira de aritmetizar algo é se você tiver uma fórmula booleana que codifica algo sobre as MTs em primeiro lugar!

Tem algo que estou perdendo? Como uma subquestão - isso significa que todos os resultados que usam o TQBF de alguma forma também não são relativizados?

cc.complexity-theory interactive-proofs relativization Henry Yuen
fonte

Você pode incluir portões oracle em uma fórmula booleana quantificada e, em seguida, um TQBF ^ O relativizado está completo para PSPACE ^ O, portanto, essa não é a etapa de não relativização.

Emil Jeřábek apoia Monica

Oi Emil - você poderia elaborar um pouco mais? Digamos que eu tenho uma máquina M e tento realizar a mesma prova de que L (M) (o idioma aceito por M) é redutível a (o que significa). Acabarei precisando criar uma fórmula booleana que expresse se duas configurações C, C 'da máquina oracle M são vizinhas (para quaisquer duas configurações C, C'). Como posso garantir, independentemente do oráculo, que esta fórmula booleana tenha tamanho finito, e muito menos tamanho polinomial? Por exemplo, O poderia codificar o problema da parada.

{P S P A C E}^{O}

${\sf PSPACE}^O$

T B Q F^{O}

$TBQF^O$

T B Q F^{O}

$TBQF^O$

Henry Yuen

Eu acho que eu poderia adiar isso ainda mais - o teorema de Cook-Levin se relativiza? Pelas mesmas razões mencionadas acima, acho que não. Se o teorema de Cook-Levin relativiza, determina se a prova de completude PSPACE do TQBF também relativiza.

Henry Yuen

Uma fórmula QBF ^ O pode, além dos quantificadores usuais e conectivos booleanos, também usar um novo portão fan-in ilimitado, vamos chamá-lo de , cuja semântica é sse os corda pertence ao oráculo . Expressar nessa linguagem que uma configuração é sucessora de outra é um exercício simples, pois você pode simplesmente conectar o conteúdo da fita de consulta do oracle em . (Estou assumindo aqui que uma máquina PSPACE só pode fazer consultas polinomialmente longas.)

f (x_{0}, \dots, x_{n})

$f(x_0,\dots,x_n)$

f (x_{0}, \dots, x_{n}) = 1

$f(x_0,\dots,x_n)=1$

x_{0} \dots x_{n}

$x_0\dots x_n$

O

$O$

f

$f$

Emil Jeřábek suporta Monica

Entendo - você está dizendo que, ao relativizar a prova da completude PSPACE do TQBF, você não apenas relativiza as máquinas em jogo, mas também relativiza as próprias fórmulas booleanas (para que elas não sejam mais fórmulas booleanas no sentido estrito ) Nesse caso, posso ver por que a etapa de aritmetização seria interrompida. Obrigado! Talvez você possa escrevê-lo como resposta.

Henry Yuen

Qualquer resposta a uma pergunta da forma "Qual é a verdadeira razão disso ..." será necessariamente um tanto subjetiva. No entanto, para o caso particular de IP = PSPACE, acho que pode-se argumentar que a aritmetização é realmente a chave, observando que, embora IP = PSPACE não seja relativizado , ele se algebriza no sentido de Aaronson e Wigderson . Como eles explicam em seu artigo, grosso modo, uma inclusão de classe de complexidade algebriza se para todos oráculos e todas as extensões de baixo grau de ${\cal C} \subseteq {\cal D}$ ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ $A$ $\tilde A$ $A$ . Em particular, eles mostram que a inclusão PSPACE IP é algebrizada, mesmo que não seja relativizada. $\subseteq$

A intuição que eu desenvolvi é que os resultados não relativizantes são aqueles que remexem no âmago da questão das Máquinas de Turing

Essa não é uma má intuição, mas acho que o resultado de Aaronson-Wigderson mostra que a prova IP = PSPACE circula de maneira bastante limitada e certamente não de maneira sofisticada o suficiente para provar P NP, já que Aaronson e Wigderson também mostram que serão necessárias técnicas não algebrizantes para separar P de NP. $\ne$

Timothy Chow
fonte

Obrigado pela referência. Deixe-me ver se entendo isso: o que você - e o artigo de Aaronson / Wigderson - parece estar argumentando é que "aritmetização" é um passo fracamente não relativizante e que uma pequena mudança natural na noção de relativização (ou seja, relativização algébrica) quebrará essa propriedade. Como o restante da prova IP = PSPACE está relativizando (e estou convencido pelo que Emil disse acima), isso significa que o resultado IP = PSPACE em si é muito fracamente não relativizante, e foi o que você disse. Muito interessante! Obrigado. Eu preciso de uma maneira de aceitar ambas as respostas :)

Henry Yuen

Sim, isso é basicamente certo.

Timothy Chow

Qual é a verdadeira razão pela qual IP = PSPACE não é relativizante?

Respostas: