You are not logged in.

|DG|Damm<

Praktikant

  • "|DG|Damm<" started this thread

Posts: 13

Date of registration: Oct 13th 2010

1

Thursday, September 6th 2012, 5:21pm

KvA Frage - Komplexität von Algorithmen

Hallo!

Wir sind in der Klausur SS'11 auf folgendes Problem gestoßen:

Behauptung: Jedes Problem das sich auf SAT reduzieren lässt, ist NP-hart.
Musterlösung: Behauptung ist falsch.

Skript S.16 sagt:
Eine Sprache B ist NP-hart, falls für alle A€NP gilt: A<=B.

Hier ist doch SAT Repräsentant für alle A€NP oder nicht? Das würde aber einen Widerspruch zur Musterlösung der Aufgabe geben.


Kann da jemand helfen?


Besten Gruß
Maurizio

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

2

Thursday, September 6th 2012, 5:35pm

Alle Probleme aus NP lassen sich *auf* SAT reduzieren. Wenn man nun SAT *auf* ein anderes Problem reduziert, dann ist dieses Problem dann natürlich NP-hart.
Jedes Problem, welches sich *auf* SAT reduzieren lässt, ist selber in NP enthalten (da SAT in NP enthalten ist).

In der Aufgabe wird behauptet, dass sich jedes Problem L, welches sich auf SAT reduzieren lässt, in Zeichen L <=_m^P SAT, NP-hart wäre. Das ist natürlich erstmal so nicht korrekt, weil wir lediglich aus L <=_m^P SAT folgern können, dass L in NP liegt.

Ändert man die Behauptung zu "Jedes Problem auf welches man von SAT aus reduzieren kann, ist NP-hart", dann wäre diese korrekt. Beachte hierbei die Änderung des "Blickwinkels".
A reduziert man auf B bedeutet A <=_m^P B.
Auf A reduziert man von B aus bedeutet B <=_m^P A.
Das Reduktionssymbol "<=_m^P" kann man folglich umgangssprachlich als "ist reduzierbar auf" lesen.

Klar geworden?

Beste Grüße,
Arne Meier
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 2 times, last edit by "Arne" (Sep 6th 2012, 5:36pm)


|DG|Damm<

Praktikant

  • "|DG|Damm<" started this thread

Posts: 13

Date of registration: Oct 13th 2010

3

Thursday, September 6th 2012, 6:08pm

Super! Ja, es war das Problem mit der Ausdrucksweise.
Wir sind von "SAT <=_m^P L" ausgegangen.


Vielen Dank für die schnelle Anwort =)