Quelle est la «vraie» raison pour laquelle IP = PSPACE n'est pas relativisant?

IP = PSPACE est répertorié comme l'exemple canonique d'un résultat non relativisant, et la preuve en est qu'il existe un oracle $O$ tel que , tandis que pour tous oracles . ${\sf coNP}^O \not\subseteq {\sf IP}^O$ ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ $O$

Cependant, je n'ai vu que quelques personnes expliquer pourquoi le résultat ${\sf IP} = {\sf PSPACE}$ ne se relativise pas, et la réponse habituelle est "arithmétisation". Après inspection de la preuve de IP = PSPACE, cette réponse n'est pas fausse , mais elle ne me satisfait pas. Il semble que la "vraie" raison remonte à la preuve que le problème TQBF - vraie formule booléenne quantifiée - est complet pour PSPACE; pour le prouver, vous devez montrer que vous pouvez encoder des configurations d'une machine PSPACE dans un format de taille polynomiale, et (cela semble être la partie non relativisante) vous pouvez encoder des transitions "correctes" entre des configurations dans une taille polynomiale formule booléenne - elle utilise une étape de style Cook-Levin.

L'intuition que j'ai développée est que les résultats non relativisants sont ceux qui se mêlent à la réalité des machines de Turing, et l'étape où TQBF se révèle être terminée pour PSPACE est où ce fouinage se produit - et l'étape d'arithmétisation pourrait 'est arrivé uniquement parce que vous aviez une formule booléenne explicite à arithmétiser.

Cela me semble être la raison fondamentale pour laquelle IP = PSPACE est non relativisant; et le mantra folklorique que les techniques d'arithmétisation ne relativisent pas semble être un sous-produit de cela: la seule façon d'arithmétiser quelque chose est si vous avez une formule booléenne qui code quelque chose sur les MT en premier lieu!

Y a-t-il quelque chose qui me manque? En tant que sous-question - cela signifie-t-il que tous les résultats qui utilisent TQBF d'une manière ou d'une autre ne relativisent pas non plus?

cc.complexity-theory interactive-proofs relativization Henry Yuen
la source

Vous pouvez inclure des portes Oracle dans une formule booléenne quantifiée, puis un tel TQBF ^ O relativisé est terminé pour PSPACE ^ O, ce n'est donc pas l'étape de non-relativisation.

Emil Jeřábek soutient Monica le

Salut Emil - pourriez-vous nous en dire un peu plus? Disons que j'ai une machine M, et j'essaie de réaliser la même preuve que L (M) (le langage accepté par M) est réductible en (quel que soit ). Je devrai éventuellement trouver une formule booléenne qui exprime si deux configurations C, C 'de la machine Oracle M sont voisines (pour deux configurations C, C' quelconques). Comment puis-je m'assurer, quel que soit l'oracle, que cette formule booléenne a une taille finie, et encore moins une taille polynomiale? Par exemple, O pourrait coder le problème d'arrêt.

{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

Je suppose que je pourrais repousser encore plus loin - le théorème de Cook-Levin se relativise-t-il lui - même ? Pour les mêmes raisons que celles mentionnées ci-dessus, je ne pense pas. La relativisation du théorème de Cook-Levin détermine si la preuve d'exhaustivité PSPACE de TQBF se relativise également.

Henry Yuen

Une formule QBF ^ O peut, outre les quantificateurs habituels et les connecteurs booléens, également utiliser une nouvelle porte fan-in illimitée, appelons-la

, dont la sémantique est que

si la chaîne

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$

appartient à l'oracle

. Exprimer dans cette langue qu'une configuration succède à une autre est un exercice simple, car vous pouvez simplement brancher le contenu de la bande de requête Oracle dans

x_{0} \dots x_{n}

$x_0\dots x_n$

O

$O$

f

$f$ . (Je suppose ici qu'une machine PSPACE ne peut effectuer que des requêtes polynomiales longues.)

Emil Jeřábek prend en charge Monica le

Je vois - vous dites que lorsque vous relativisez la preuve de l'intégralité de PSPACE de TQBF, non seulement vous relativisez les machines en jeu, mais vous relativisez également les formules booléennes elles-mêmes (elles ne sont donc plus des formules booléennes au sens strict). ). Dans ce cas, je peux voir pourquoi l'étape d'arithmétisation échouerait. Merci! Vous pouvez peut-être l'écrire comme réponse.

Henry Yuen

Toute réponse à une question du formulaire "Quelle est la vraie raison pour laquelle ..." sera nécessairement quelque peu subjective. Cependant, pour le cas particulier de IP = PSPACE, je pense qu'il est assez judicieux de démontrer que l'arithmétisation est en effet la clé, en observant que si IP = PSPACE ne se relativise pas , elle algebrize au sens d' Aaronson et Wigderson . Comme ils l'expliquent dans leur article, en gros, une inclusion de classe de complexité algébrique si pour tous les oracles et toutes les extensions de bas degré de ${\cal C} \subseteq {\cal D}$ ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ $A$ $\tilde A$ . En particulier, ils montrent que l'inclusion PSPACE IP algébrie, même si elle ne se relativise pas. $A$ $\subseteq$

L'intuition que j'ai développée est que les résultats non relativisants sont ceux qui se mêlent aux moindres détails des machines de Turing

Ce n'est pas une mauvaise intuition, mais je pense que le résultat d'Aaronson-Wigderson montre que la preuve IP = PSPACE fait le tour d'une manière assez limitée, et certainement pas d'une manière suffisamment sophistiquée pour prouver P NP, car Aaronson et Wigderson aussi montrent que des techniques non algébriantes seront nécessaires pour séparer P de NP. $\ne$

Timothy Chow
la source

Merci pour la référence. Permettez-moi de voir si je comprends cela: ce que vous - et l'article d'Aaronson / Wigderson - paraissez soutenir, c'est que l '"arithmétisation" est une étape faiblement non relativisante, et qu'un petit changement naturel à la notion de relativisation (à savoir, relativisation algébrique) brisera cette propriété. Étant donné que le reste de la preuve IP = PSPACE est relativisant (et je suis convaincu par ce que Emil a dit ci-dessus), cela signifie que le résultat IP = PSPACE lui-même est très peu relativisant, ce que vous avez dit. Très intéressant! Merci. J'ai besoin d'un moyen d'accepter les deux réponses :)

Henry Yuen

Oui, c'est fondamentalement vrai.

Timothy Chow

Quelle est la «vraie» raison pour laquelle IP = PSPACE n'est pas relativisant?

Réponses: