Diskussion:3-SAT

Es darf keine konjunktive Normalform, sondern nur eine konjunktive Form sein. Die konjunktive Normalform fordert explizit, dass alle Variablen in jedem Term vorkommen. Gerade in der Formulierung mit maximal drei Variablen in jedem Term ist das nicht mehr zutreffend und die einzelnen Terme sind dann auch keine Max-Terme. (nicht signierter Beitrag von 37.201.181.93 (Diskussion) 16:03, 10. Apr. 2021 (CEST))

"3-SAT lässt sich wiederum u.a. auf das Cliquenproblem, das Rucksackproblem und auf den gerichteten Hamiltonkreis (DHC) polynomial reduzieren, wodurch auch diese Probleme als NP-schwer nachgewiesen sind."

Die Probleme werden nicht als NP-schwer nachgewiesen sondern als NP-vollständig. Bitte verbessern.
Docterx 23:22, 18. Jan. 2007 (CET)

Soweit ich weiß ist 3-SAT nicht "höchstens 3 Literale pro Klausel", sondern "genau 3 Literale pro Klausel". Für die Möglichkeiten der darstellbaren Probleme ist dies keine Einschränkung, da eine 1-Literal-Klausel durch doppeltes wiederholen des Literals als 3-Literal-Klausel dargestellt werden kann. siehe z.B.: http://www.inf.uni-konstanz.de/algo/lehre/ss04/ti/skript/komplexitaet.pdf Abschnitt 6.22

ich kenne es als höchstens 3, aber wie Du ja oben schon beschrieben hast, ist das eine in das andere überführbar, also gibt's eigentlich kein Problem, oder? --Pinguin.tk 18:28, 24. Aug 2004 (CEST)

Yup, hab nochmal weiter gesucht, "höchstens 3" reicht aus, benutzt nur bei meisten Sachen die ich gemacht habe das "genau 3". Insofern kein Problem... ;)

dann ist ja gut, danke für's nachschauen! Pinguin.tk 16:08, 25. Aug 2004 (CEST)

Also nach der Definition von Karp sieht es mEn so aus, dass "3SAT" exakt 3 Literale haben muessen, daneben existiert noch "MAX3SAT", was dann wohl das hier beschriebene ist.. hat aber mit dem inhaltlich scheint es ja wurscht zu sein. Man muss halt schauen woran man sich orientiert, denke da wir hier eins von den 21 haben, waere es eventuell besser, das auch so darzustellen. :-) Bei Probleme ausserhalb dieses Kontextes mags egal sein, habe sowohl 2SAT, MAX2SAT als auch EXACT2SAT schon gesehen - "gefuehlt" scheint mir der Wechsel zwischen ySAT und MAXySAT aber haeufiger zu sein als zwischen ySAT und EXACTySAT. Google? --Schwarzer8Kater 22:59, 18. Feb. 2008 (CET)

Die Formulierung ist auch in sofern nicht so sinnvoll als dass sich 3-SAT auf jedes NP-vollständige Problem und "viele" andere Probleme (Halteproblem etc.) reduzieren lässt. --80.134.131.137 14:02, 18. Jul. 2010 (CEST)

Vergleich mit allen NP-vollständigen Problemen

"Wie bei allen NP-vollständigen Problemen ist es einfach bzw. in kurzer Zeit möglich, für eine gegebene Belegung der Variablen zu testen, ob sie F wahr macht, aber "schwierig", eine passende Belegung zu finden."

Das ist doch irgendwie Unsinn: Die wenigsten NP-vollständigen Probleme haben mit Belegungen von Variablen zu tun. Selbst bei anderer Formulierung (Überprüfen eines Lösungsvorschlags ist einfach) bleibt die Aussage zweifelhaft. Oft kann auch noch ein bestimmter Lösungsvorschlag nicht effizient auf Wahrheit geprüft werden. Was bedeutet diese Aussage z.B. für das "Traveling Salesman"-Problem? Der Test ob eine bestimmte Route die kürzeste ist, ist genauso aufwendig, wie das Originalproblem zu lösen, nämlich die kürzeste Route zu finden.

Du verwechselst hier Entscheidungs- und Optimierungsprobleme. Der Begriff NP-vollständig bezieht sich auf Entscheidungsprobleme, d.h. auf Probleme die eine Ja-Nein-Frage darstellen. Traveling Salesman ist in seiner urspünglichen Version ein Optimierungsproblem. Es lässt sich aber ein dazugehöriges Entscheidungsproblem angeben, nämlich "existiert eine Rundreise kürzer als x?" Für eine vorgeschlagene Rundreise ist das einfach zu überprüfen, die allgemeine Antwort ist aber schwierig zu geben.

Der von dir kritisierte Satz ist aber trotzdem schwammig, ich werde ihn ausbessern.

Noch ein kleiner Hinweis: Es ist hier üblich, Diskussionsbeiträge mit --~~~~ zu unterschreiben.--MKI 23:21, 17. Aug 2005 (CEST)

keine konjunktive Normalform

Hi,

"3-Sat ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik (Erfüllbarkeit engl.: satisfiability, kurz SAT).

Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform vorliegende aussagenlogische Formel F, die höchstens 3 Literale pro Klausel enthält, erfüllbar ist."

Die darauf folgende Formel F ist keine konjunktive Normalform.

Grüße síkhs

Wenn du uns noch erklären kannst, warum dass keine KNF ist, können wir das auch reparieren. Für mich sieht das wie eine KNF aus. --Koethnig 13:06, 29. Dez. 2007 (CET)

Hi Koething,

schau mal unter KNF nach, da habe ich das erklärt. Es geht hier im wesentlichen um den Aspekt der Vollständigkeit. Eine KNF besteht ja aus konjunkitv verknüpfen Maxtermen. Damit wäre auch schon alles gesagt, denn ein Maxterm ist ein Term, der vollständig ist, dessen disjunktiv verknüpfte Literale also genau einmal drin vorkommen (Definition Maxterm). So steht es in meinem Skript.

edit: da bei dem Problem 3-Sat eine Klauselmenge gefordert ist, sollte das vielleicht noch ergänzt werden. Jedoch wenn man von einer KNF spricht, dann ist die Formel definitiv falsch.

Grüße síkhs

Hi,

also danke nochmal für die ertragreiche Diskussion im wiki-Artikel KNF. - Da scheinbar in der Literatur und an den deutschen Hochschulen der Konsens, was die Definition einer KNF (DNF) betrifft, ein Verschiedener ist, führt eine Diskussion bzgl. dieses Artikels wohl nicht weiter zum Ziel. Um jedoch alle Wissensabspaltungen abzudecken und die aus Diesen resultierenden Missverständnisse bzgl. dieses wiki-Artikels zu kompensieren, schlage ich vor, hinter den Begriff "konjunktive Normalform" in Klammern ein "(Klauselmenge)" zu setzen; so wie es auch bei Uwe Schöning, Theoretische Informatik - kurzgefasst, 4.Auflage, S.164 zu sehen ist.

Alt = "Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform vorliegende aussagenlogische Formel F, die höchstens 3 Literale (...)"

Neu = "Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform (Klauselform) vorliegende aussagenlogische Formel F, die höchstens (...)"

Es mag vielleicht etwas spitzfindig erscheinen, jedoch schließt man so, bei einer bestimmten Menge an wiki-Lesern (und das sind mind. diejenigen aus meinem Studiengang (c.a. 400 Leute), wenn nicht noch alle diejenigen, die an der selben Hochschule vor mir Informatik studiert haben) Missverständnisse aus :-)

Grüße síkhs

3-SAT enthält 2-SAT

Sehe ich das richtig, dass alle 2-SAT-Probleme in 3-SAT enthalten sind? Die Begrenzung der Anzahl der Literale pro Klausel ist ja nach oben begrenzt - nicht aber nach unten.

Ich denke, dass deshalb nicht alle 3-SAT-Problem-Instanzen NP-schwer sind (die "Sprache" 3-SAT selbst natürlich schon). Deshalb würde ich lieber nicht schreiben "Alle k-SAT Probleme für k>=3 sind NP-vollständig", sondern lieber "Alle Probleme aus k-SAT \ 2-SAT für k>=3 sind NP-vollständig." -- oder alternativ etwas schwächer "Alle k-SAT Probleme für k>=3 sind NP-schwer". Ich nehme hier an, dass mit k-SAT Problem nicht die ganze Sprache bezeichnet wird sondern eine Problem-Instanz aus 3-SAT.

Macht das Sinn? Wenn ja, könnte man dadurch den Artikel aufwerten!

--82.135.86.87 13:39, 28. Jul. 2010 (CEST)

Mit k-SAT-Problem ist die ganze Sprache gemeint ("Wenn ich dir irgendeine Formel mit bestimmter Form nenne, kannst du dann herausfinden, ob sie erfüllbar ist?"), und nicht eine einzelne Instanz ("Ist diese eine Formel erfüllbar?"). Damit verschwindet das aufgeworfene Problem: Es gibt nur ein 3-SAT-Problem, und dieses ist NP-vollständig. Für einzelne Formeln nach NP-Vollständigkeit zu fragen, ist sinnlos, da es keine variable Eingabegröße mehr gibt, von der man die Laufzeit polynomiell abhängig machen könnte.

Dass es Unterklassen eines Problem gibt, welche schneller entschieden werden können, ändert nichts an der Komplexität des Problems. Ein anderes Beispiel: Vergleichsbasiertes Sortieren von Listen hat die Laufzeit O(n log n), aber wenn man nur die Unterklasse der Listen betrachtet, deren Elemente natürliche Zahlen zwischen 1 und einer Konstanten k sind, kann man diese mit Bucketsort in O(n) sortieren. --91.13.218.142 11:31, 25. Sep. 2010 (CEST)

Beweis der NP-vollständigkeit von MAX-3-SAT

Um die NP-Vollständigkeit zu zeigen, müsste meines Wissens nach 3-SAT auf MAX-3-SAT reduziert werden. Und nicht wie es hier steht MAX-3-SAT auf 3-SAT. LG Göttertöter (14:25, 5. Feb. 2017 (CET), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

So schwer?

Das die Lösung des Problems so schwer sein soll erstaunt schon irgendwie. Ich habe in ein paar Minuten mehrere Belegungen durch Ausschluss finden können (Term x_i kommt inn Disjunktion 1, aber nicht 2 vor etc.) und damit relativ schnell Belegungen gefunden, bei der eine wahre Aussage zustande kommt. Warum sollte ein Computer dies nicht mit einer ähnlichen Vorgehensweise in polynomialer Zeit lösen können? --95.91.242.234 10:08, 16. Mai 2022 (CEST)