Pourquoi P = NP n'implique-t-il pas P = AP (c'est-à-dire P = PSPACE)?

Il est bien connu que si $\mathbf{P}=\mathbf{NP}$ puis la hiérarchie polynomiale effondre et $\mathbf{P}=\mathbf{PH}$ .

Cela peut facilement être compris par induction en utilisant des machines Oracle. La question est - pourquoi ne pouvons-nous pas poursuivre le processus inductif au-delà d'un niveau constant d'alternances et prouver $\mathbf{P}=\mathbf{AltTime}(n^{O(1)})$ (alias $\mathbf{AP}=\mathbf{PSPACE}$ )?

Je cherche une réponse intuitive.

La preuve pour $\mathbf{P}=\mathbf{AltTime}(O(1))$ ( $=\mathbf{PH}$ ) est une induction utilisant $\mathbf{P}=\mathbf{NP}$ . L'induction montre que pour tout nombre naturel $k$ , $\mathbf{P}=\mathbf{AltTime}(k)$ (et $\mathbf{AltTime}(O(1))$ est juste leur union).

L'induction ne fonctionne pas lorsque le nombre d'alternances peut changer avec la taille d'entrée (c'est-à-dire lorsque le nombre d'alternances possibles de la machine n'est pas un nombre mais une fonction de la taille d'entrée, c'est-à-dire que nous ne montrons pas qu'une exécution de la machine sur une seule entrée peut être réduite à aucune alternance, nous montrons que les exécutions de la machine sur toutes les entrées peuvent être "uniformément" réduites à aucune alternance).

Regardons une déclaration similaire mais plus simple. Nous voulons montrer que la fonction identité domine finalement toutes les fonctions constantes ( f « g ssi pour tous , mais un nombre fini n f ( n ) ≤ g ( n ) ). Cela peut être prouvé par exemple par induction. Pour tout k , k ≪ n (c'est-à-dire f k ≪ i d où f k ( n ) = $id(n)=n$$f \ll g$$n$ $f(n) \leq g(n)$$k$$k \ll n$$f_k \ll id$$f_k(n)=k$), mais nous ne l'avons pas pour les fonctions non constantes comme , n 2 ≪ ̸ n .$n^2$$n^2 \not \ll n$

Comparez la hiérarchie polynomiale avec la hiérarchie pour les preuves interactives. Si pour certains k fixes , vous avez k alternances dans une preuve interactive - IP ( k ) - la classe de complexité résultante n'a pas plus de puissance que ce que vous obtenez avec deux alternances - c'est-à-dire IP ( k ) = IP (2 ) = AM (en supposant que k ≥2). Cependant, si vous autorisez un nombre d'alternances polynomiales, vous obtenez la classe de complexité IP = PSPACE, qui est censée être beaucoup plus grande que AM, une classe est contenue dans Π ₂ P, au deuxième niveau de la hiérarchie polynomiale. Donc, ce phénomène se produit réellement (bien que, à notre connaissance, avec la hiérarchie polynomiale).

Cela se produit car la réduction qui prend un problème de taille n dans IP ( k ) et le transforme en problème dans IP (2) fait exploser la taille du problème, de sorte que, même pour toute IP spécifique ( k ), le problème reste de taille polynomiale , si vous laissez k varier, la réduction résultante ne donne pas de problèmes polynomiaux en k .

Voici une petite intuition concernant l'écart entre alternances constantes et illimitées: une opération polynomiale répétée un nombre constant de fois est polynomiale, mais répétée un nombre polynomial de fois peut être exponentielle. Par exemple, prenez la multiplication répétée sur elle-même:

v = 2
for(i=1 to n)
  v = v*v

Le nombre d'itérations est linéaire et la sortie est exponentielle. Mais si vous fixez n, c'est un polynôme sur la taille de la valeur initiale.

Ci-dessous, je développe un peu le point de la réponse de Peter en essayant de supprimer le quantificateur pendant plus d'un nombre constant d'étapes pour voir où il échoue et si quelque chose peut être récupéré d'une telle tentative.

Essayons d'amplifier $\mathsf{P}=\mathsf{NP}$ pour des nombres plus que constants.

Supposons que $\mathsf{P}=\mathsf{NP}$ . Il existe donc une machine temporelle polynomiale qui résout Ext-Circuit-SAT (existe-t-il une extension satisfaisante pour un circuit donné et une affectation partielle à ses entrées?).

Plus formellement, nous avons un algorithme de polytime $A$ avec un temps d'exécution polynomial $p(n)\in\rm{poly}(n)$ st

Étant donné un circuit booléen $\varphi$ , et une affectation partielle $\tau$ aux entrées,
$A$ renvoie "oui" s'il y a une extension de $\tau$ qui satisfait $\varphi$ , et renvoie "non" sinon.

Pour dépasser des temps constants, nous devons effectuer la suppression du quantificateur efficacement. Nous pouvons le faire parce que le théorème de Cook-Levin est un théorème constructif, en fait il donne un algorithme de temps polynomial $Cook$ st

Étant donné un DTM $M$ recevant deux entrées et trois nombres unaires $n$ , $m$ et $t$ ,
$Cook(M, n, m, t)$ renvoie un circuit booléen de taille $O(t^2)$ qui simule $M$ sur des entrées de longueur $(n,m)$ pour $t$ étapes.

Essayons de les utiliser pour étendre l'argument de $\mathsf{P}=\mathsf{PH}$ pour obtenir un algorithme résolvant TQBF (en fait TQBCircuit, c'est-à-dire un problème de circuit booléen totalement quantifié).

L'idée de l'algorithme est la suivante: nous utilisons à plusieurs reprises $Cook$ sur $A$ pour supprimer les quantificateurs d'un circuit quantifié donné. Il y a un nombre linéaire de quantificateurs, nous espérons donc obtenir un algorithme polynomial temporel (nous avons un algorithme avec plusieurs étapes polynomiales utilisant le sous-programme polynomial temporel $Cook$ ). À la fin de ce processus d'élimination des quantificateurs, nous aurons un circuit sans quantificateur qui peut être évalué en temps polynomial (le problème de la valeur du circuit est en $\mathsf{P}$ , soit$CV$ un algorithme de temps polynomial pour calculer la valeur du circuit d'un circuit donné) .

Cependant, nous verrons que cette idée ne fonctionne pas (pour la même raison que Peter l'a souligné).

• Soit $\varphi$ un circuit quantifié, (initialisé à la formule quantifiée donnée).
• Soit $k$ le nombre de quantificateurs dans $\varphi$ .

• Pour $i$ de $k$ à $1$ do

  • Soit $\psi$ = $Qx_k \sigma(x_1,...,x_k)$ le dernier quantificateur et la partie libre de quantificateur.

  • Si $Q = "\exists"$ ,

    1. Calculer $C = Cook(A, |\sigma|, |x_1|+...+|x_k-1|, p)$ ,
    2. Remplacez les bits d'entrée par $\sigma$ dans le circuit $C$ ,
    3. Remplacez $\psi$ par $C$ dans $\varphi$ .

  • Si $Q = "\forall"$ ,

    1. Considérez $\psi$ comme $\lnot \exists x_k \lnot \sigma$ ,
    2. Calculer $C = Cook(A, |\lnot \sigma|, |x_1|+...+|x_k-1|, p)$ ,
    3. Remplacer les bits d'entrée par $\lnot \sigma$ dans le circuit $C$ ,
    4. Remplacez $\psi$ par le $\lnot C$ dans $\varphi$ .
• Calculer et renvoyer $CV(\varphi)$ .

L'algorithme résultant ressemble au temps polynomial: nous avons plusieurs étapes polynomiales, chaque étape est calculable en temps polynomial. Cependant ce n'est pas correct, l'algorithme n'est pas du temps polynomial.

L'utilisation de sous-programmes de temps polynomial dans un algorithme de temps polynomial est du temps polynomial. Le problème est qu'en général, cela n'a pas besoin d'être vrai si les valeurs retournées par les sous-programmes ne sont pas de taille polynomiale dans l'entrée d'origine et nous supposons que nous faisons des affectations sur les valeurs renvoyées par les sous-programmes. (Dans le modèle TM, nous devons lire la sortie de tout sous-programme de temps polynomial bit par bit.) Ici, la taille de la valeur renvoyée par l'algorithme $Cook$ augmente (peut être une puissance de la taille de l'entrée qui lui est donnée) , la puissance exacte dépend du temps de fonctionnement de $A$ et se situe autour de $p^2(|input|)$, donc puisque nous savons que $A$ ne peut pas être inférieur au temps linéaire, $|output|$est au moins $|input|^2$ ).

Le problème est similaire au code simple ci-dessous:

• Étant donné $x$ ,
• Soit $n = |x|$,
• Soit $y = x$ ,
• Pour $i$ de $1$ à $n$ do
  • Soit $y = y^{|y|}$, (ie concaténation de $|y|$ copies de $y$ )
• Retour y

Chaque fois que nous exécutons $y = y^{|y|}$nous égalons la taille de $y$ . Après $n$ exécutions, nous aurons un $y$ qui est $x^{2^n}$ et qui a la taille $n2^n$ , évidemment pas un polynôme dans la taille de l'entrée.

Supposons que nous considérons uniquement les formules quantifiées avec $k(n)$ alternances de quantificateurs (où $n$ est la taille totale de la formule quantifiée).

Supposons que $A$ s'exécute dans le temps $p$ (par exemple, le temps linéaire qui n'est pas exclu jusqu'à présent), et avoir peut-être un algorithme $Cook$ efficace produisant un circuit plus petit de taille $l(t)$ à la place de $t^2$ , alors nous obtenons un algorithme pour ExtCircuitSat qui s'exécute dans le temps $(l\circ p)^{O(k)}(n)=\underbrace{l(p(l(p(\dots(l(p(n)))))))}_{O(k)\mbox{ compositions}}$ . Même dans le cas où$l$et$p$étaient linéaires (mais avec un coefficient totaln))et sik(n)=Θ(n)il seraitΩ(n2n)$a\geq 2$ ) nous obtiendrions un algorithme qui fonctionne dans le temps$\Omega(n2^{k(n)})$$k(n) = \Theta(n)$$\Omega(n2^n)$ similaire à l'algorithme de force brute (et même cela était basé sur l'hypothèse que Cook-Levin peut être effectué sur des algorithmes résultant de circuits de taille linéaire dans le temps d'exécution de l'algorithme).

Je pense que c'est parce qu'à chaque niveau du PH, le nombre d'alternances est constant (c'est-à-dire indépendant de la taille d'entrée), alors qu'en AP, le nombre d'alternances peut être illimité (mais polynomial dans la taille de l'entrée).