Komplexitätstheorie co-NP Beweis

Neue Frage »

jaaaa Auf diesen Beitrag antworten »
Komplexitätstheorie co-NP Beweis
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. Im voraus vielen Dank!
URL Auf diesen Beitrag antworten »
RE: Komplexitätstheorie co-NP Beweis
Und warum erzählst du uns das alles nochmal? unglücklich
jaaaa Auf diesen Beitrag antworten »
RE: Komplexitätstheorie co-NP Beweis
weil ich dachte, dass ich den Titel falsch ausgewählt habe..unglücklich
Neue Frage »
Antworten »



Verwandte Themen

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