Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Blatt 8 Aufgabe 43, Reduktion IS auf BP
Hey,
ueberseh ich etwas bei folgendem Beweis oder ist’s wirklich nicht mehr?
Zu zeigen: Es gibt eine Polynomzeitreduktion von IS auf BP.
Wir haben in der Vorlesung gezeigt: BP ist NP-schwer, d.h. Fuer jede Sprache L in NP, insbesondere IS, gibts eine Polynomialzeitreduktion von L auf BP.
Viele Gruesse
Nee nee. Sie sollen schon eine direkte Reduktion angeben, also die Independent-Set-Frage als binäres Programm hinschreiben … auch vor dem Hintergrund, daß es Programme zu kaufen gibt, die BP lösen. Wenn Sie also ein derartiges Programm erworben haben, können Sie es zur Lösung des Independent-Set-Problems einsetzen, sobald Sie die gewünschte Formulierung durchgeführt haben.
MfG
Rolf Wanka