Conséquences de

Nous savons que si alors tout le PH s'effondre. Et si la hiérarchie polynomiale s'effondre partiellement? (Ou comment comprendre que le PH pourrait s'effondrer au-dessus d'un certain point et non en dessous?)$P=NP$

En termes plus courts, quelles seraient les conséquences de et ?P ≠ N $NP=coNP$$P\ne NP$

Pour moi, l'une des conséquences les plus élémentaires et les plus surprenantes de est l'existence de preuves courtes pour toute une série de problèmes où il est très difficile de voir pourquoi elles devraient avoir des preuves courtes. (Cela revient en quelque sorte à prendre du recul par rapport à "Quelles autres implications en termes de complexité cet effondrement a-t-il?" À "Quelles sont les raisons très basiques et terre-à-terre que cet effondrement serait surprenant?")$\mathsf{NP}=\mathsf{coNP}$

Par exemple, si , alors pour chaque graphique qui n'est pas hamiltonien, il existe une courte preuve de ce fait. De même pour les graphiques qui ne sont pas tricolores. De même pour les paires de graphes qui ne sont pas isomorphes. De même pour toute tautologie propositionnelle .$\mathsf{NP}=\mathsf{coNP}$

Dans un monde où , la difficulté de prouver des tautologies propositionnelles n'est pas que certaines tautologies courtes ont des preuves longues - parce que dans un tel monde chaque tautologie a une preuve polynomiale courte - mais plutôt qu'il y en a autre raison pour laquelle nous ne pouvons pas trouver ces preuves efficacement.$\mathsf{P} \neq \mathsf{NP} = \mathsf{coNP}$

Si nous supposons également , l'hypothèse entraînerait également l'effondrement des classes randomisées:$\mathsf{NP}=\mathsf{RP}$ . Bien que tous ces éléments soient conjecturés pour s'effondrer inconditionnellement dans P , de toute façon, il est encore possible que cela se produise. En tout cas, N P = c o N P ne semble pas impliquer en soi que ces classes randomisées s'effondrent.$\,\,\mathsf{ZPP}=\mathsf{RP}=\mathsf{CoRP}=\mathsf{BPP}$$\mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$

S'ils ne le font pas, c'est-à-dire que nous avons au moins , alors, avec seulement l' hypothèse N P = c o N P , cela aurait une autre conséquence importante:$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$ . Celasuitepartirun résultat de Babai, Fortnow, Nisan et Wigderson, qui dit que si touteslangues unaire (tally) dans P H tombent P , alors B P P = P . Ainsi, si B P P ≠ P , alors ils ne peuvent pas tous tomber en P , comme la N P = c o N P hypothèse implique P H = N P . Par conséquent, il doit y avoir un langage de pointage en N P - $\,\,\mathsf{E}\neq \mathsf{NE}$$\mathsf{PH}$$\mathsf{P}$$\mathsf{BPP}=\mathsf{P}$$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$$\mathsf{PH}=\mathsf{NP}$$\mathsf{NP}-\mathsf{P}$. Enfin, la présence d'une langue de pointage dans est bien connu pour impliquer E ≠ N E .$\mathsf{NP}-\mathsf{P}$$\mathsf{E}\neq \mathsf{NE}$

Les émissions de raisonnement qui précède l'effet intéressant que le hypothèse, en dépit d' être un effondrement, amplifie en fait la séparation de la puissance de B P P ≠ P , comme celui - ci seuls ne sont pas connues pour impliquer E ≠ N E . Cette "anomalie" semble soutenir la conjecture B P P = P .$\mathsf{NP}=co\mathsf{NP}$$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{E}\neq \mathsf{NE}$$\mathsf{BPP}= \mathsf{P}$

Il y a deux définitions pour compter les classes au - delà . L'un a été défini par Valiant et l'autre a été défini par Toda.${\bf \#P}$

Pour toute classeC, définissez#C=∪ A ∈ C (#P) A , où( # P A)signifie les fonctions comptage des chemins d'acceptation des machines de Turing à temps polynomial non déterministe ayantApour oracle.${ \rm \underline {Valiant's-Definition:}}$$C$$\#C =\cup_{A\in C}(\#P)^{A}$$({\#P}^A)$$A$

Selon la définition de Valiant, nous avons déjà ${\bf \#NP} = {\bf \#CoNP}$

Pour toute classeC, définissez#. Cpour être la classe de fonctionsftelle que pour certainsC-prédicats à deux arguments calculablesRet certains polynômesp, pour chaque chaînex,elle contient:f(x)=| | {y| p(${ \rm \underline {Toda's-Definition:}}$$C$$\# .C$$f$$C-$$R$$p$$x$et R ( x , y ) } | | .$f(x)=||\{y|p(|x|)=|y|$$R(x,y)\}||$

Selon la définition de Toda, nous avons si et seulement si N P = C o N P .${\bf \#.NP} = {\bf \#.CoNP}$${\bf NP} = {\bf CoNP}$

Ensuite , si l' on suppose que nous aurait F P de # P .${\bf P}\not = {\bf NP}$${\bf FP} \not = {\bf \# P}$

Ker-i Ko a montré qu'il y a un oracle qui fait s'effondrer le PH au niveau k-ème. Voir "Ker-I Ko: hiérarchies temporelles polynomiales relativisées ayant des niveaux exactement K. SIAM J. Comput. 18 (2): 392-408 (1989)".