Ist es möglich, dass co-np= p aber np!= P

Question

Angenommen, es gibt einen Algorithmus, der sich als eine unbefriedigbare SAT-Formel eingibt, und es nicht in der Polynomzeit überprüft.Wenn der Eingang jedoch eine ergiebige Formel ist, funktioniert es nicht (sagen wir nicht Zeit- und Erinnerungsprobleme, der Algorithmus wird in der Argumentation verloren).

dann co-np= p, da wir unatissierbare Instanzen in der Polynomzeit überprüfen können.Das Zertifikat der Unzufriedenheit ist die Formel selbst.

aber dann ist es immer noch möglich, dass p!= np?

Answer 1

Wenn CO- $ \ Mathsf {NP}=mathsf {p} $ dann $ \ mathsf {NP}=text {co -} \ mathsf {p}=mathsf {p} $ .

Answer 2

Die Antwort ist nein, und der Grund ist, dass $ \ mathrm {p} $ unter Ergänzungen trivial geschlossen ist.Nur per Definition von $ \ mathrm {co} $ folgt der $ \ mathrm {conp}=mathrm {p} $ ist gleichwertig mit $ \ mathrm {np}=mathrm {cop} $ , und verwenden wir diesen $ \ mathrm {cop}=mathrm {p} $ Zum Schluss, dass $ \ mathrm {conp}=mathrm {p} $ iFF $ \ mathrm {NP}=mathrm {p} $ .

Answer 3

Sei x ein Problem in NP, dh es gibt einen einfachen Beweis, wenn die Antwort ja ist.Nehmen Sie nun das Problem X ': "Hat X die Antwort nein?Das ist in Co-NP, also wäre es in p, also x ISIN P.