Doppelpost! Gute Charakterisierung co-NP |
26.11.2018, 15:32 | jaaaa | Auf diesen Beitrag antworten » |
Gute Charakterisierung co-NP 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! |
||
30.11.2018, 10:54 | 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 |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |