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.
Reduktion P-Problem auf NP-Problem
In den Braindumps auf der FSI-Seite findet sich in fast allen Altklausuren eine Aufgabe, in der man ein Problem, welches relativ offensichtlich in P liegt auf ein Problem aus NP reduzieren soll. Beispielsweise aus dem WS 15/16 Aufgabe 6:
Gegeben ist folgende Sprache: SUMME={bin(a1)#:::#bin(an) | n>= 2 , alle ai unterschiedlich}
Reduzieren Sie in Polynomzeit SUMME <= SAT
Soll man hier einen Entscheider für Summe angeben oder reicht es kurz zu begründen, warum SUMME in P liegt?
1 „Gefällt mir“
Es reicht aus (plausibel) zu begründen warum SUMME in P liegt. Danach kann man annehmen man hat einen polynomiellen Entscheider für SUMME.
Zum Beispiel kann man hier argumentieren:
-Ob die Syntax passt - mindestens ein # - kann man in polynomieller Zeit entscheiden
-Man kann die Gleichheit von zwei durch Binärdarstellung repräsentierte Zahlen in polynomieller Zeit bezüglich der Länge der Binärdarstellungen entscheiden.
-Man muss hier nur O(n^2) viele Paare prüfen
-Sowohl n als auch die Länge der 0-1-Folgen sind polynomiell in der Eingabelänge
-Entsprechend ist die Gesamtlaufzeit ebenfalls Polynomiell
Achtung: n entspricht hier nicht der Eingabelänge!!! (n entspricht hier der Anzahl der ai)
PS: Ich glaube nicht, dass die Sprache SUMME jemals so definiert wurde, da darin gar keine Summe vorkommt. Diese Sprache hieß glaube ich ALLE_UNGLEICH 
2 „Gefällt mir“