Diskussion:Erfüllbarkeitsproblem der Aussagenlogik

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Erfüllbarkeitsproblem der Aussagenlogik“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen, und unterschreibe deinen Beitrag bitte mit oder --~~~~.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Frage

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)

Die Problemstellung ist insofern vereinfacht, dass das Problem für Menschen einfacher erscheint.

Die Komplexität ist genau dieselbe, also ist das 3-SAT nicht leichter zu lösen als SAT.

--zeno 23:56, 10. Jan 2005 (CET)

Ich war mal so frei, wenigstens die Definition von 3-SAT im Artikel zu erwähnen.--AlfonsGeser 20:47, 23. Mai 2008 (CEST)

SAT-Solver auf Deutsch?

Gibt es eigentlich einen schönen deutschen Begriff für SAT-Solver? Ich frage deswegen, weil bereits Leute daran sind, Artikel in Wikipedia über das Thema zu schreiben.--AlfonsGeser 20:47, 23. Mai 2008 (CEST)

Ich habe mal etwas mehr über SAT-Solver eingefügt und die NP-Vollständigkeit näher erläutert.--AlfonsGeser 22:31, 23. Mai 2008 (CEST)

Beispiel

Man sollte ein Beispiel bringen: Eine (nicht triviale) aussagenlogische Formel mit nur einer Belegung, die sie erfüllt.

--MauriceKA 17:13, 18. Jun. 2008 (CEST)

Es wird lang und breit getreten, was für eine Bedeutung SAT für NP-Vollständigkeit hat usw, aber der einzige erklärende/definierende Satz lautet: "Es fragt, ob eine aussagenlogische Formel erfüllbar ist" bei dem alle 3 nicht-trivialen Worte Links sind. Das wäre so als ob ich mich stundenlang über die Verwendung der Primzahlen bei der Kryptographie auslasse und als Definition lediglich "ist durch nur 2 natürliche Zahlen teilbar" hinterlasse... Das ist alles nicht falsch, aber ohne Studium weiterer Quellen nutzlos.

Der Wikipediaartikel bringt einem Laien nichts!!!

Was heißt das hier: Es fragt, ob eine aussagenlogische Formel erfüllbar ist. Was heißt das? Was ist eine aussagenlogische Formel? Frech formuliert: 30g Zucker und 100ml Wasser ist ne Formel für ein Getränk. Ist erfüllbar.

Quellen / Belege

Eine grundlegende Änderung des Artikels wurde heute so begründet:

Komplette Neukonzeption und Erweiterung des Artikels. Wichtige Grundlagen und die wichtigsten Algorithmen und ihre Konzepte werden erläutert. Die Länge des Artikels ist denke ich angemessen für das wichtigste schwere Problem der Algorithmik. Die einzelnen Kapitel sind so gehalten, dass sie gerade so weit ins Detail gehen, wie es für das Verständnis der Konzepte erforderlich ist, aber Details weglassen, die man z.B. in einem eigenen Artikel des Kapitels erwähnen würde. Quellen: Paper/Konferenzen

Die Quellenangabe ist somit NULL, eigentlich müßte das ganze zurückgesetzt werden. Da ich aber weder Ahnung vom noch Interesse am Thema habe, setze ich den Baustein und überlasse anderes den Kollegen mit Ahnung und Interesse. --PCP (Disk) 12:15, 9. Nov. 2020 (CET)

Lag es an dem fehlenden references-Tag und dem Kapitel Einzelnachweise? Das ist repariert. --Mbssdr (Diskussion) 12:49, 9. Nov. 2020 (CET)

Nein, es liegt an der Angabe: "Quellen: Paper / Konferenzen" das ist nicht nachvollziehbar. --PCP (Disk) 14:33, 9. Nov. 2020 (CET)

Tut mir Leid, bin neu hier. Was genau fehlt? Die Quellen sind alle im Artikel aufgeführt und im Text referenziert, wie bei wissenschaftlicher Arbeit üblich. Im Kommentar zur Bearbeitung war noch genau ein Zeichen übrig und die Lösung kann ja auch nicht sein, dort 23 Quellen aufzulisten.--Mbssdr (Diskussion) 15:07, 9. Nov. 2020 (CET)

Hallo, danke dir für deine große Bearbeitung. Ich finde die von dir angegebenen Quellen sind im Allgemeinen wohl ausreichend und scheinen auch den Richtlinien für Wikipedia:Belege zu entsprechen (ohne dies eingehend geprüft zu haben). Es wird wohl noch ein bisschen dauern bis andere Autoren weitere Kleinigkeiten korrigiert und die Änderungen gesichtet haben.--BlauerBaum (Diskussion) 21:40, 9. Nov. 2020 (CET)

Da auch keiner der anderen Autoren die Quellen bemängelt hat entferne ich mal den Hinweis auf fehlende Quellen, der ja nicht zutrifft.--Mbssdr (Diskussion) 21:32, 13. Nov. 2020 (CET)

Webseiten der SAT-Association

Folgende Webseiten sind aktuell im Artikel verlinkt:

• http://www.satcompetition.org/
• http://satisfiability.org/
• http://satassociation.org/
• http://jsatjournal.org/

Sie scheinen alle von der selben Person/Organisation (sat association) zu stammen (unter anderem da alle lediglich ein selbst signiertes TLS-Zertifikat haben und bei dem selben Registrar sind). Ich habe jedoch keine Seite gefunden die eindeutig die Zusammengehörigkeit der 4 Webseiten/Organisationen zeigt, es wäre wohl wünschenswert das auf einen Weblink zu reduzieren.--BlauerBaum (Diskussion) 22:02, 9. Nov. 2020 (CET)

Viele Webseiten von Konferenzen, nicht-kommerziellen Instituten etc. muten leider eher provisorisch an. Ich würde am ehesten die SAT-Association drin lassen, von da kann man sich auch zu den anderen Seiten durchschlagen, wenn man möchte. Ich würde aber vorschlagen die Competition auch drinzulassen, da der Wettbewerb für sich interessant ist und der interessierte Nutzer da vielleicht gerne draufklicken würde. --Mbssdr (Diskussion) 00:22, 10. Nov. 2020 (CET)