NP Vollständigkeit < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo
Ein Entscheidungsproblem C ist NP-Vollständig, genau dann wenn:
(1) C ist in NP.
(2) Alle Probleme in NP lassen sich auf C reduzieren.
Folgende Frage:
Habe Beweise (in Büchern) gefunden um zu beweisen, dass ein Entscheidungsproblem C NP-Vollständig ist, indem vorgegangen wurde im Stil:
(a) C ist in NP.
(b) Ein spezifisches Problem, welches NP-Vollständig ist, lässt sich auf C reduzieren.
Wieso kann man von (b) auf das (2) schliessen von oben?
Könnte mir jemand auf einen Beweis verweisen, oder kann mir helfen selber auf die Sprüunge zu kommen?
Oder habe ich etwas völlig falsch verstanden?
Vielen Dank.
mathwizard
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:52 Mi 23.01.2008 | | Autor: | Gilga |
Ganz einfach.... erst auf "Ein spezifisches Problem, welches NP-Vollständig ist" reduzieren und dann auf C reduzieren.
für all A aus NP gilt:
A reduzierbar auf B
B reduzierbar auf C
=> A reduzierbar auf C
|
|
|
| |
|
Danke für die schnelle Antwort.
Ich scheine aber ganz hohl zu sein, denn ich verstehe immer noch nicht 
(Oder meinst du man muss die Reduktion in Beide Richtungen machen? Dachte - falls ich das nicht falsch verstanden habe - das muss man gerade nicht tun.)
Nehmen wir also ein Beispiel, das ![[]](/images/popup.gif) SUBSET-SUM Problem. Um es einfach zu machen: Entscheidung ist, ob sich die Zahlen zu 0 summieren.
Man kann nun 3-SAT auf SUBSET-SUM reduzieren. (Den Beweis dazu kenne ich). Und nehmen wir an wir wissen, dass 3-SAT NP-Vollständig ist.
Wie können wir nun daraus schliessen, dass SUBSET-SUM auch NP-Vollständig ist?
(Weil,... hier liegt mein Problem... von der anderen Seite betrachtet wissen wir, dass 3-SAT NP-Vollständig ist, dann müsste jedoch SUBSET-SUM auch reduzierbar sein auf 3-SAT, falls es NP-Vollständig ist, oder?)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:27 Do 24.01.2008 | | Autor: | bazzzty |
> (Oder meinst du man muss die Reduktion in Beide Richtungen
> machen? Dachte - falls ich das nicht falsch verstanden habe
> - das muss man gerade nicht tun.)
Neinnein, nur in eine Richtung.
> Nehmen wir also ein Beispiel, das
> SUBSET-SUM Problem [..]
>
> Man kann nun 3-SAT auf SUBSET-SUM reduzieren. (Den Beweis
> dazu kenne ich). Und nehmen wir an wir wissen, dass 3-SAT
> NP-Vollständig ist.
Da 3-Sat NP-vollständig ist, gilt ja insbesondere auch (2): Alles Probleme in NP lassen sich auf 3-Sat reduzieren. Wenn wir jetzt wissen, daß sich 3-Sat auf SUBSET-SUM reduzieren läßt, dann impliziert das, daß sich jedes Problem aus NP auf SUBSET-SUM reduzieren läßt: Man kann es erst auf 3-Sat reduzieren (geht nach Voraussetzung) und dann auf SUBSET-SUB (geht nach dem Beweis).
> Wie können wir nun daraus schliessen, dass SUBSET-SUM auch
> NP-Vollständig ist?
Es liegt in NP und man kann jedes Problem aus NP darauf reduzieren.
> (Weil,... hier liegt mein Problem... von der anderen Seite
> betrachtet wissen wir, dass 3-SAT NP-Vollständig ist, dann
> müsste jedoch SUBSET-SUM auch reduzierbar sein auf 3-SAT,
> falls es NP-Vollständig ist, oder?)
Ja, aber. Daß man SUBSET-SUM auf 3-SAT reduzieren kann, folgt daraus, daß SUBSET-SUM in NP ist, und man von 3-SAT schon weiß, daß man *jedes* Problem aus NP darauf reduzieren kann.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:15 Do 24.01.2008 | | Autor: | mathwizard |
Danke
Der springende Punkt ist der Satz von Cook, welcher erlaubt die Schleife zu schliessen. (weshalb man die Reduktion dann auch nur einseitig machen muss... gegeben dass die Reduktion transitiv ist, was man ja auch zeigen kann...)
|
|
|
|
