NP-Vollständigkeitsbeweis < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:21 Di 24.07.2012 | | Autor: | Sin777 |
| Aufgabe | | Zwei Boolsche Formeln [mm] F_{1}, F_{2} [/mm] heißen nicht-äquivalent, wenn es eine Belegung gibt, die genau eine der beiden Formeln erfüllt. Zeigen sie, dass NÄ = [mm] \{(F_{1},F_{2}):F_{1}\mbox{ und }F_{2}\mbox{ sind nicht äquivalent}\} [/mm] NP-vollständig ist. |
Hallo, ich habe diese Aufgabe in einer Altklausur bei uns gefunden. Ich habe noch so meine Schwierigkeiten mit der NP-Vollständigkeit und wollte fragen, ob mir jemand erklärt, wie man zeigen kann, dass die obige Menge NP-vollständig ist.
Ich denke mal, ich muss eine Reduktion auf SAT durchführen. Wie könnte da die Abbildungsvorschrift lauten? Weiterhin weiß ich nicht, wie ich zeigen kann, dass die Menge in NP liegt.
Ich bin wirklich sehr dankbar über jede Nachricht :)
Viele Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:42 Mi 25.07.2012 | | Autor: | Sin777 |
Mh, gibt es einen Grund, warum niemand antwortet? :)
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:29 Mi 25.07.2012 | | Autor: | Herby |
Hallo Sin777,
> Mh, gibt es einen Grund, warum niemand antwortet? :)
ich denke schon, sogar mehrere:
* es sind gerade nur Leute im Forum unterwegs, die das nicht beantworten können - fehlende Kenntnisse zum Thema (so wie ich ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]") )
* vielleicht hat jemand Kenntnisse, aber keine Zeit
* vielleicht hat jemand verborgene Kenntnisse und muss sie erst einmal für sich auffrischen
Da du ja gerade hier nachfragst und ich davon ausgehe, dass du immer noch an einer Antwort interessiert bist, habe ich die Fälligkeit mal bis übermorgen verlängert. Wenn du eine weitere Verlängerung wünschst, dann melde dich einfach.
Grüße
Herby
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:57 Fr 27.07.2012 | | Autor: | felixf |
Moin!
> Zwei Boolsche Formeln [mm]F_{1}, F_{2}[/mm] heißen
> nicht-äquivalent, wenn es eine Belegung gibt, die genau
> eine der beiden Formeln erfüllt. Zeigen sie, dass NÄ =
> [mm]\{(F_{1},F_{2}):F_{1}\mbox{ und }F_{2}\mbox{ sind nicht äquivalent}\}[/mm]
> NP-vollständig ist.
> Hallo, ich habe diese Aufgabe in einer Altklausur bei uns
> gefunden. Ich habe noch so meine Schwierigkeiten mit der
> NP-Vollständigkeit und wollte fragen, ob mir jemand
> erklärt, wie man zeigen kann, dass die obige Menge
> NP-vollständig ist.
>
> Ich denke mal, ich muss eine Reduktion auf SAT
> durchführen. Wie könnte da die Abbildungsvorschrift
> lauten? Weiterhin weiß ich nicht, wie ich zeigen kann,
> dass die Menge in NP liegt.
Ein Tipp: $a [mm] \mathop{\mathrm{XOR}} [/mm] b$ ist genau dann wahr, wenn genau einer von $a$ und $b$ wahr ist. Damit solltest du das ganze auf ein normales SAT zurueckfuehren koennen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:31 Mi 01.08.2012 | | Autor: | Sin777 |
Also ich tue mir noch sehr schwer mit der NP-Vollständigkeit und würde einen solchen Beweis gerne einmal an einem einfachen Beispiel nachvollziehen. Dafür eignet sich diese Aufgabe ganz gut, denke ich :)
Also ich muss zunächst zeigen, dass NÄ [mm] \in [/mm] NP liegt und dann noch eine Funktion f finden, so dass x [mm] \in [/mm] SAT <=> f(x) [mm] \in [/mm] NÄ.
Dazu "rate" ich zunächst eine entsprechende Belegung, so dass [mm] F_{1} [/mm] erfüllt und [mm] F_{2} [/mm] nicht erfüllt ist. Die Länge der akzeptierenden Berechnung ist gemäß dem Beweis für die NP-Vollständigkeit in polynomieller Zeit möglich. Also NÄ [mm] \in [/mm] NP.
Nun weiß ich aber nicht richtig, wie ich diese Funktion wählen soll. Sei [mm] F_{1} \in [/mm] SAT, dann ist [mm] f(F_{1}) [/mm] = [mm] (F_{1},F_{2}). [/mm] Aber wie muss ich [mm] F_{2} [/mm] wählen, bzw. wie bringe ich das in Verbindung mit der XOR-Funktion?
Ich würde mich sehr freuen, wenn du mir das verraten würdest :)
Viele Grüße
|
|
|
| |
|
Hi!
Der Tipp mit dem XOR ist eigentlich Gold wert, aber ich habs auch nicht auf Anhieb gesehen, wie man ihn verwenden kann.
Also was hast Du gegeben?:
SAT: Formel in KNF, d.h. sowas in der Form (A [mm] \vee [/mm] B) [mm] \wedge [/mm] (C [mm] \vee [/mm] D) [mm] \wedge [/mm] (A [mm] \vee [/mm] D [mm] \vee [/mm] E [mm] \vee [/mm] Z)
2 Formeln [mm] F_1, F_2, [/mm] die "ähnlich" aufgebaut sind, d.h. es gibt eine Belegung [mm] \alpha [/mm] die für beide Formeln aufjedenfall gültig ist. (Eine Belegung setzt die Prädikate auf "konkrete" Werte, also z.B: A=T, B=T, [mm] C=\prep [/mm] etc)
Sei nun [mm] \alpha [/mm] eine Belegung für [mm] F_1, [/mm] sodass [mm] F_1 [/mm] mit dieser Belegung (also [mm] [F_1]_{\alpha} [/mm] - hoffe Du kennst die Schreibweise) z.B. nach true ausgewertet wird, also : [mm] [F_1]_{\alpha}=T
[/mm]
Dann kann [mm] F_2 [/mm] mit dieser Belegung vollkommen anders ausgewertet werden, z.B. [mm] [F_2]_{\alpha}=\perp
[/mm]
In diesem Beispiel wären also [mm] F_1 [/mm] und [mm] F_2 [/mm] nicht äquivalent, weil [mm] \alpha F_1 [/mm] wahr macht, aber [mm] F_2 [/mm] nicht.
Nun kommt die XOR-Funktion ins Spiel:
[mm] F_1 [/mm] XOR [mm] F_2 [/mm] ist immer genau dann wahr, wenn [mm] [F_1]_{\alpha} \not=[F_2]_{\alpha}, [/mm] d.h. wenn [mm] F_1 [/mm] und [mm] F_2 [/mm] unter einer gleichen Belegung unterschiedlich ausgewertet werden.
Genau das möchtest Du ja herausfinden.
Nun zur Reduktion:
[mm] F_1 [/mm] XOR [mm] F_2 \equiv (F_1 \vee F_2) \wedge (\neg F_1 \vee \neg F_2) [/mm] (wenn Du es nicht direkt siehst, macht Dir eine Wertetabelle oder schau mal hier http://de.wikipedia.org/wiki/XOR-Verkn%C3%BCpfung )
Und das ist im Kern schon deine Reduktion.
Du musst die Formeln [mm] (F_1 \vee F_2) \wedge (\neg F_1 \vee \neg F_2) [/mm] jetzt nur noch in eine SAT Form bringen, d.h. die KNF bilden. Den Algo. dafür wirst Du/"Ihr" sicherlich behandelt haben.
Ich hoffe das hilft Dir beim Verständnis. Lass dich nicht von einer komplexen Schreibweise verwirren, eigentlich ist Logik immer recht einfach, wenn man auf die Schreibweise mal klar kommt. Ist halt alles schön logisch :D
Gruß
Pille
|
|
|
|
