La question ouverte NP = co-NP est-elle la même que P = NP?

12

Je me demande cela en se basant sur plusieurs endroits en ligne qui appellent co- un problème ouvert majeur ... mais je ne trouve aucune indication quant à savoir si c'est la même chose que Problème ...N P P = N PNP=NPP=NP

Mirrana
la source

Réponses:

20

Non. C'est un autre problème ouvert et certainement lié, mais différent. La classe de complexité co- NP est l'ensemble des langages dont les compléments sont en NP ; c'est-à-dire l'ensemble des problèmes de décision pour lesquels une réponse "non" a un vérificateur déterministe en temps polynomial. Ainsi, par exemple, la question "Cette formule SAT est-elle insatisfaisante?" Si la réponse est "non", alors il y a une affectation satisfaisante des variables qui le prouve; c'est le certificat du vérificateur.

Il est possible que , mais N P = co- N PPNPNP=NP .

Mais d'autre part, si , alors N P = co- N P à coup sûr. En effet , si une langue est en P , alors son complément est également en P , donc si P = N P , alors cela vaut pour toutes les langues N P ainsi.P=NPNP=NPPPP=NPNP

usul
la source
4
aussi si NP coNP alors P NP car P est fermé sous complément. donc la question NP ? = coNP peut être aussi dur que l'infâme P ? = Problème NP. =?=?
vzn
2
Oui, bon point!
usul
1
en plus de cela, je viens de voir une affirmation dans un article que NP = coNP est largement admis.
vzn
4

Une bonne façon de répondre à cette question est d'utiliser la hiérarchie polynomiale (PH) (voir aussi ici ). La hiérarchie polynomiale est une hiérarchie de classes de complexité qui généralise les classes , N P et c o - N P aux machines Oracle et les utilise comme échellePNPcoNP pour mesurer la complexité des problèmes.

On sait que si ou P = N P alors la hiérarchie polynomiale s'effondre à son premier niveau.NP=coNPP=NP

Reza
la source