Doppelpost! Gute Charakterisierung co-NP

Neue Frage »

jaaaa Auf diesen Beitrag antworten »
Gute Charakterisierung co-NP
Meine Frage:
Hallo zusammen,

Könnte mir jemand von euch bei meiner Aufgabe helfen?

Aufgabenstellung wäre:
Nehmen Sie an, dass NP co-NP. Es folgt ein Beweis, dass Komplement von 3-SAT eine gute Charakterisierung hat.
Entscheiden Sie , ob dieser Beweis korrekt ist, oder nicht. Begründen Sie Ihre Antwort.
Beweis:
1) 3-SAT ist in NP, da es NP-vollständig ist. Daraus folgt, dass Komplement von 3-SAT in co-NP liegt.
2) Komplement von 3-SAT liegt in NP, da folgender Verifizierer angegeben werden kann: Sei das Zertifikat eine Belegung der Variablen. Falls jede Klausel ein Literal mit dem Wert true enthält, dann antworte NEIN, sonst JA.
3)Nach Definition von guter Charakterisierung gilt somit: Komplement von 3-SAT hat eine Gute Charakteriesierung.


Meine Ideen:
Meine Idee wäre:
Beweis ist nicht korrekt.
Definition von guter Charakterisierung bedeutet, dass es sowohl für Ja- als auch für Nein Instanzen Zertifikate gibt, die in polinomieller Zeit geprüft werden können.
#Gilt NP co-NP, so ist kein co-NP-vollständiges Problem in NP. => Das sagt, dass ein Problem mit einer guten Charakterisierung wahrscheinlich nicht NP-vollständig ist.

Wäre so richtig? Ich freue mich auf eure Hilfe. Voraus vielen Dank!
Steffen Bühler Auf diesen Beitrag antworten »
RE: Gute Charakterisierung co-NP
Hier geht's weiter: Komplexitätstheorie co-NP Beweis

Dieser Thread ist geschlossen.

Viele Grüße
Steffen
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »