WikiDer > Zufriedenheitsproblem

In dem Komplexitätstheorie verweist es Erfüllungsproblem (auch bekannt als SAT, aus dem Englischen Erfüllbarkeit) um zu bestimmen, ob a logische Aussageerfüllt kann werden; ein Satz kann erfüllt werden, wenn es eine Zuschreibung von gibt richtig oder falsch zum Atomformeln existiert so, dass der gesamte Satz wahr ist.

Definition

Das Erfüllbarkeitsproblem ist a Entscheidungsproblem, ein Ja/Nein-Problem, mit als Eingabe a logische Aussage. Das Problem ist nun: Gibt es eine Zuschreibung von richtig oder falsch zum Atomformeln so dass der ganze Satz wahr ist? Der Vorschlag ${displaystyle (p_{1}Rinder p_{2})Keil (zB p_{1}Rinder p_{3})Keil (p_{2}Rinder p_{5})}$ ist zum Beispiel erfüllbar, weil der Satz mit p . erfüllt werden kann₂ = wahr und p₃ = wahr.

Häufig verwendete Begriffe in diesem Bereich sind:

• Buchstäblich: ein Atomformel oder der Negation davon zum Beispiel ${displaystyle p}$ und ${Anzeigestil zB p}$.
• Klausel (auf Englisch: Klausel): ein Disjunktion von Literalen, zum Beispiel ${displaystyle p_{1}Rinder p_{2}Rinderegge p_{3}}$.
• Konjunktive Normalform: ein Verbindung von Klauseln, zum Beispiel ${displaystyle (p_{1}Rinder p_{2})Keil (zB p_{1}Rinder p_{3})Keil (p_{2}Rinder p_{5})}$.

Anwendungen

In der Lage zu sein, Erfüllbarkeitsprobleme zu lösen, ist in vielen Bereichen der Informatik, wie Theoretische Informatik, Algorithmen, künstliche Intelligenz, design von Hardware- und Überprüfung von Hardware und Software. Viele mathematische und praktische Probleme, wie z Diagrammfärbung und Scheduling-Aufgaben, als Erfüllbarkeitsproblem kodiert werden. Es bietet eine Möglichkeit, das Problem als logische Aussage zu kodieren. Dieser Satz kann durch einen Algorithmus untersucht werden, der die Erfüllbarkeit untersucht. Wenn sich der Satz als erfüllbar erweist, gibt es auch eine Lösung für das ursprüngliche Problem.

Varianten

Es gibt viele Varianten des Erfüllbarkeitsproblems, wie zum Beispiel CNF-SAT (ist eine Formel in formula Konjunktive Normalform erfüllbar?) oder k-SAT (ist eine Formel in normaler Konjunktivform mit exaktem kLiterale pro Klausel erfüllbar?). Viel untersuchte Varianten von k-SAT sind 2-SAT und 3-SAT. Da jede Aussageformel in konjunktiver Normalform beschrieben werden kann, wird viel über die Erfüllung von Formeln in dieser Form geforscht. Betrachtet man die Erfüllbarkeit von a Verbindung von Hornklauseln man spricht vom Problem HORNSAT (Hornerfüllbarkeit).

Ein verwandtes Problem ist MAX-SAT, das nach der maximalen Anzahl von Klauseln in einer Formel in normaler Konjunktivform sucht, die erfüllt werden kann. Diese Bedingungen können kombiniert werden; auf diese Weise erhält man Probleme wie MAX-3-SAT, die die maximale Anzahl von Klauseln suchen, die in einer Formel in normaler Konjunktivform mit drei Literalen pro Klausel erfüllt werden können.

NP-Vollständigkeit

Das Erfüllbarkeitsproblem ist a NP-vollständigEntscheidungsproblem. Es ist auch das erste Problem, für das NP-Vollständigkeit demonstriert wurde, nämlich durch Stephen Cook 1971. Auch die Variante, bei der man Formeln in konjunktiver Normalform betrachtet, die genau drei Literale pro Klausel haben, ist NP-vollständig (3-SAT). Das Problem 2-SAT ist nicht NP-vollständig, aber NL-komplett; das Problem 2-SAT kann auch in sein Polynomzeit gelöst werden. Das Problem HORNSAT ist P-voll. Dafür gibt es einen Algorithmus, der das Problem in polynomieller Zeit löst.

Das Problem MAX-SAT ist NP-hart. Die MAX-Variantek-SAT ist NP-schwer für k ≥ 2.

Lösen

Es gibt alle Arten Algorithmen zur Lösung von Erfüllbarkeitsproblemen, wie z Auflösung und der DPLL-Algorithmus. Ein Computerprogramm oder Algorithmus zur Lösung eines Erfüllbarkeitsproblems heißt a SAT-Löser. Manchmal ist es auch möglich, die Erfüllbarkeit einer logischen Formel anhand einer Darstellung zu bestimmen, wie z binäres Entscheidungsdiagramm.

Einige Algorithmen und/oder Computerprogramme sind: BirkeMin,^[1]Spreu,^[2]DPLL-Algorithmus, GRIFF, March_dl,^[3]MiniSAT,^[4]POSITION, rel_sat, Auflösung und SATO.

Zwei gängige Ansätze sind "konfliktgetrieben" und "Schau voraus": bei konfliktgetrieben erkennt man, wenn eine Erfüllung nicht mehr möglich ist und kehrt zu einem früheren Punkt im Algorithmus zurück, um die Suche von dort aus fortzusetzen Suchraum so klein wie möglich, indem man nach vorne schaut. Dies ist rechenzeitaufwendig, kann aber den Algorithmus in Richtung einer guten Lösung lenken.

Lokale Suche

Es gibt auch stochastische Suchalgorithmen für das Erfüllbarkeitsproblem, wie z GSAT, CSAT, SpaziergangSAT und Neuheit. Es gibt keine Garantie dafür, dass diese Algorithmen eine Lösung finden, wenn sie existiert. Auch ist es mit diesen Algorithmen nicht möglich, die Unerfüllbarkeit einer Formel zu ermitteln (es sei denn, man prüft alle möglichen Zuordnungen). Diese Algorithmen berücksichtigen wahre oder falsche Zuweisungen zu allen atomaren Formeln; Dies ist der Suchraum des Algorithmus. Durch wiederholtes Invertieren eines Wahrheitswerts (zum Beispiel durch Umwandeln von p = true in p = false) versucht der Algorithmus, mehr Klauseln wahr zu machen. Die Algorithmen unterscheiden sich beispielsweise darin, welche atomare Formel gewählt wird, um den Wahrheitswert zu ändern.

Die Algorithmen beginnen mit einer zufälligen Zuweisung von wahr und falsch und die Wahrheitswerte werden eine vorbestimmte Anzahl von Malen geändert. Wenn sich die gesamte Formel nicht als wahr erwies, startet der Algorithmus mit einer neuen zufälligen Zuweisung von wahr oder falsch zu allen atomaren Formeln neu. Die Suche beginnt dann erneut, jedoch von einem anderen Startpunkt im Suchraum.

Externe Links

• (und) SAT und MAX-SAT für den Laien-Forscher
• (und) Die Webseite der internationalen SAT-Wettbewerbe, jährliche Wettbewerbe
• (und) Die International Conferences on Theory and Applications of Satisfiability Testing (SAT)