Diskussion:Erfüllbarkeitsproblem der Aussagenlogik
aus Wikipedia, der freien Enzyklopädie
Bezieht sich SAT wirklich schon auf konjunktive Normalformen? IMHO nennt man das Problem dann CNF-SAT. --Esperantisto 12:06, 11. Jun 2004 (CEST)
Problematische Formulierung: "Das Problem 3-SAT ist eine vereinfachte Variante, die sich aber polynomial reduzieren lässt..." - Bedeutet dies, dass die Reduktion selbst polynomiale Laufzeit besitzt, oder dass 3-SAT polynomial entscheidbar ist? (14. Jun 2004 CEST) - Ich bin mir jetzt fast sicher, dass die Reduktion in polynomialer Laufzeit möglich ist, das 3-SAT Problem selbst jedoch wie das allgemeine SAT-Problem NP-vollstaendig ist. (21. Jun 04)
muss die Formulierung nicht anders herum heißen: SAT läßt sich polynomial reduzieren auf 3SAT? (vgl. Hopcroft/Motwani/Ullman, Automatentheorie, 2002, S. 444 und S. 326 in Zsh mit Unentscheidbarkeit: "Die Richtung der Reduktion ist wichtig. Häufig wird der Fehler begangen, den Beweis für die Unentscheidbarkeit eines Problems P2 über die Reduktion von P2 auf ein als unentscheidbar bekanntes Problem P1 zu führen. Es soll also die Aussage "wenn P1 entscheidbar ist, dann ist auch P2 entscheidbar" gezeigt werden. Diese Aussage ist zwar mit Sicherheit richtig, jedoch nutzlos, da deren Hypothese "P1 ist entscheidbar" falsch ist ... Ein bekanntes unentscheidbares Problem P1 muss auf P2 reduziert werden." (16. Juni 2004)
Das ist irreführend: "Das Problem 3-SAT ist eine vereinfachte Variante," - inwiefern ist 3-SAT gegenüber SAT vereinfacht? Die Komplexität ist bei beiden dieselbe. Auch suggeriert die Verwendung von "3-SAT" auf der einen Seite aber die Verwendung von "Erfüllbarkeitsproblem der Aussagenlogik" auf der anderen Seite, dass diese beiden verschieden sind. Ich würde eher schreiben: Das Problem 3-SAT ist eine Variante, die sich in polynomieller Zeit auf SAT reduzieren lässt. (21. Jun 04)
