Diskussion:3-SAT
aus Wikipedia, der freien Enzyklopädie
"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)
[Bearbeiten] 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)
