Komplexitätstheorie co-NP Beweis |
26.11.2018, 19:51 | jaaaa | Auf diesen Beitrag antworten » |
Komplexitätstheorie co-NP Beweis 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! |
||
26.11.2018, 20:05 | URL | Auf diesen Beitrag antworten » |
RE: Komplexitätstheorie co-NP Beweis Und warum erzählst du uns das alles nochmal? |
||
26.11.2018, 20:09 | jaaaa | Auf diesen Beitrag antworten » |
RE: Komplexitätstheorie co-NP Beweis weil ich dachte, dass ich den Titel falsch ausgewählt habe.. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|