Est-il possible que co-np= p mais np!= P

Question

Supposons qu'il existe un algorithme qui prend comme entrée une formule SAT insatisfaite et ne manque jamais de le vérifier en temps polynomial.Toutefois, lorsque l'entrée est une formule satisfaisante, elle ne fonctionne pas (disons des problèmes de temps et de mémoire, l'algorithme se perd dans le raisonnement).

alors co-np= p parce que nous pouvons vérifier des instances insatisfiables en temps polynomial.Le certificat d'insatisfabilité est la formule elle-même.

Mais alors est-il toujours possible que p!= np?

Answer 1

si co- $ \ mathsf {np}=mathsf {p} $ $ thin $ \ mathsf {np}=texte {co -} \ mathsf {p}=mathsf {p} $ .

Answer 2

La réponse est non, et la raison est que $ \ mathrm {p} $ est trivialement fermé sous complément.Juste par définition de $ \ mathrm {CO} $ , il suit que $ \ mathrm {conion}=mathrm {p} $ équivaut à $ \ mathrm {np}=mathrm {flic} $ , puis nous utilisons cette $ \ mathrm {flic}=mathrm {p} $ pour conclure que $ \ mathrm {conion}=mathrm {p} $ iff $ \ mathrm {np}=mathrm {p} $ .

.

Answer 3

Soit X un problème dans NP, ce qui signifie qu'il existe une simple preuve chaque fois que la réponse est oui.Maintenant, prenez le problème X ': "X a-t-il la réponse non".C'est dans CO-NP, il serait donc en p, donc x isine p.