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.
Frage zu Polynomialzeitreduktion
Es geht um den Braindump vom 2013.
Im Forum hat jemand das hier als Lösung gepostet:
Meine Fragen/Unklarheiten wären jetzt die folgenden:
- Stimmt das?
- Ich kann in Polynomzeit entscheiden, ob eine gegebene 01#-Folge ∈ ER ist, richtig? Dann kann ich auch mit minimalstem Mehraufwand eine gültige SAT-Belegung (hier einfach ) zurückgeben. Damit gilt dann x∈ ER → f(x) ∈ SAT und ich konnte das in Polyzeit bestimmen, was ja die Definition von der Polyzeit-Reduktion ist. Was ich nicht verstehe, ist, wie das mit den Beispielen aus der Vorlesung und mit den meisten Übungsaufgaben zusammenhängt. Da haben wir ja in mühevollster Kleinarbeit versucht, eine gültige 3-SAT-Belegung als Graphen darzustellen, um 3SAT auf 3COL zu reduzieren. Dazu mussten wir uns überlegen, wie der Graph aussehen muss und es war ein direkter Zusammenhang zwischen den beiden Problemen ersichtlich.
Meine Fragen dazu: - Liegt die Tatsache, dass die Polyzeit-Reduktion 3SAT auf 3COL so viel umfangreicher ist, daran, dass beide Probleme ∈ NP sind? Wenn nicht, woran dann?
- Was ich als ER gegeben habe, taucht ja in dieser Funktion in keinster Weise in der SAT-Belegung auf. Das war ja meiner Meinung nach bei 3SAT auf 3COL
nicht der Fall. Wenn ich als Eingabe {100#10#11110} ∈ ER habe und einfach nur zurückgebe, was genau habe ich dann bewiesen?
Ich hoffe, dass man meine Fragen nachvollziehen kann.
Ich denke das sollte stimmen. Aber man sollte noch ENDERIESIG in polynomzeit entscheiden. Also konkret einen Algorithmus dafür angeben. (Das hab ich zumindest meinen Übungsleiter gefragt und er hat dies bejaht).
Wenn ich diesen Typ von Aufgabe richtig verstanden habe. Ist die Idee das Problem ENDERIESIG zu entscheiden und entsprechend oder 0 auszugeben. Also ist dein Wort in ENDERIESIG gibst du einfach aus, ansonsten eine 0.
Zu 3. würde ich dir zustimmen. Ist auch der einzige Unterschied.
- Bewiesen hast du, dass ENDERIESIG “leichter ist” als SAT. Und das war dir ja intuitiv auch klar, denk ich jetzt mal.
Das interessant an der Aufgabe ist ja nur, dass sobald die P=NP-Frage beantwortet werden kann, jede Sprache die in P ist auch gleichzeitig NP-vollständig ist.
Ich hoffe ich konnte etwas helfen.
OK. Ein polynomieller Verifizierer wäre dann so was wie:
-Addiere alle Ziffern von a[sub]0[/sub] bis a[sub]n-1[/sub]
-Überprüfe, ob die Summe < a[sub]n[/sub]
Die Schwierikeit bei der Polynomreduktion liegt ja darin eine total berechenbare Reduktionsfunktion anzugeben, die ein Problem in Polynomzeit auf ein anderes reduziert. Ist ein Entscheidungsalgorithmus bekannt, der in Polynomzeit läuft, dann ist diese Polynomreduktion meistens recht einfach, weil du durch den polynomiellen Entscheider deine Reduktionsfunktion einfach hinschreiben kannst (wie in dieser Klausuraufgabe eben angegeben). Bei einer Reduktion eines NP-vollständigen Problems auf ein anderes ist es eben nicht mehr so trivial, weil du x \in 3SAT nicht in Polynomzeit bestimmen kannst. In einem solchen Fall musst du dann, wie in der Vorlesung durchgeführt, zeigen, dass du das gegebene Problem in Polynomzeit zumindest so umbauen kannst, dass es sich wie das andere Problem verhält. Das ist natürlich deutlich aufwändiger, weil du dich sehr viel mehr mit der Struktur der beiden Probleme beschäftigen musst.
Professor Wanka hätte aber bestimmt nichts dagen, wenn du in der Klausur einfach einen Polynomzeitalgorithmus für SAT angibst und die Aufgabe dann damit löst - das würde vieles vereinfachen ;).
Aha, das hilft mir schon sehr viel weiter. Dankeschön!
Am Niveau meiner Fragen sollte klar sein, dass er sich da keine allzu großen Hoffnungen machen braucht 