Conséquences de problèmes complets pour NP intersecte coNP

Quelles sont les conséquences d'avoir des problèmes complets dans ?$NP\cap coNP$

Il s'agit d'un problème (large) ouvert; comme dans, on ne sait presque rien. Plus précisément, en raison de la difficulté à prouver les problèmes complets de $NP \cap coNP$ , nous avons besoin de techniques de preuve très différentes de celles qui existent actuellement. En tant que tel, une discussion sur les conséquences devrait raisonnablement inclure une tangente sur «Qu'est-ce que cela signifierait d'avoir des techniques de preuve aussi puissantes et nouvelles?

Pour une discussion relativement récente du sujet, il y a la 26e colonne NP-Completeness de David Johnson dans ACM Transactions on Algorithms from 2007 ( PDF ). Permettez-moi de paraphraser une partie de ce que David dit concernant la question de prouver l'existence de problèmes $NP \cap coNP$ -complet et d'ajouter mes réflexions:

Actuellement, nous n'avons que des candidats «faibles» et naturels à l'adhésion à $NP \cap coNP - P$ dans le sens où la preuve la plus solide de leur appartenance est que nous n'avons pas encore réussi à leur trouver d'algorithme de temps polynomial. Il énumère quelques candidats: SMALL FACTOR, SIMPLE STOCHASTIC GAME et MEAN PAYOFF GAME. Une partie de la «bizarrerie» supplémentaire de ces problèmes provient des meilleurs temps d'exécution heuristiques pour les résoudre, par exemple, SMALL FACTOR, alias INTEGER FACTOR $\le k$ , a une complexité temporelle aléatoire de $poly(n) 2^{\sqrt{k log(k)}}$ . (Si des problèmes complets existent dans$NP \cap coNP - P$, alorscetemps d'exécutionsous-exponentiel(ni purement exponentiel, ni tout à fait polynomial) est-ilendémique de la classe?)

Donc , plus précisément, nous voulons prouver quelque chose comme: problème A est seulement $P$ ssi $NP \cap coNP = P$ , soit un résultat complet comme le théorème de Cook pour 3SAT et $NP$ . Pour $NP$ , ces preuves impliquent universellement des réductions du temps polynomial (et fixent vos restrictions supplémentaires préférées, par exemple les réductions Cook, les réductions Karp). Par conséquent, dans les techniques de réduction du temps polynomial, il doit y avoir une représentation reconnaissable du temps polynomial de la classe. Pour $NP$ , nous pouvons utiliser des machines de Turing non déterministes qui s'arrêtent au sein d'un polynôme, $p(|x|)$ , nombre d'étapes. Commesouligne David, nous avonsreprésentations similaires pourautres classes (où le statut est plus clair) tels que$PSPACE$ et#$P$ .

La difficulté, cependant, de fournir une représentation similaire pour $NP \cap coNP$ est que l'analogue "naturel" nous permet d'intégrer le problème de l'arrêt dans la représentation et est donc indécidable . Autrement dit, considérons la tentative suivante de représenter $NP \cap coNP$ avec deux machines de Turing non déterministes qui, prétendument, reconnaissent des langages complémentaires:

Question: Une machine de Turing $M^*$ s'arrête-t-elle sur l'entrée $x \in {0,1}^n$ ?

Construisez deux machines de Turing à temps linéaire $M_1$ et $M_2$ comme suit. Sur l'entrée $y$ , $M_1$ lit l'entrée et accepte toujours. $M_2$ rejette toujours sauf si $|y| \ge |x|$et $M^*$ accepte $x$ aux étapes $\le |y|$.

Par conséquent, $M_1$ et $M_2$ acceptent des langages complémentaires si $M^*$ ne s'arrête pas à l'entrée $x$ . Par conséquent, par contradiction, décider si deux machines de Turing à temps polynomial acceptent des langages complémentaires est indécidable.

Ainsi, la représentation "naturelle" des problèmes $NP \cap coNP$ n'est pas reconnaissable en temps polynomial. La question demeure: comment représentez-vous les problèmes $NP \cap coNP$ sorte qu'ils soient reconnaissables en temps polynomial?

Il n'y a eu aucun travail important fait sur cette question, mais sa résolution réussie est nécessaire de prouver l' exhaustivité dans $NP \cap coNP$ . Par conséquent, je prétends que l'existence d'une technique de preuve qui peut résoudre l'intégralité de $NP \cap coNP$ sera la plus grande histoire ici - et non les résultats "automatiques" de $NP \cap coNP$ problèmes complets ( par exemple des classes de complexité, peut-être en train de s'effondrer) dont nous sommes déjà conscients (ou plutôt, nous le serons , hypothétiquement dans le futur).