Ähnliche Themen
    Suchen
     
     

    Ergebnisse in:
     


    Rechercher Fortgeschrittene Suche

    Die neuesten Themen
    » Friedrich Ernst Dorn
    Mo Okt 16, 2017 9:17 am von Andy

    » **** Platin ****
    Mo Okt 16, 2017 9:11 am von Andy

    » Der Aufruf der Kulturschaffenden
    Mo Okt 16, 2017 9:02 am von Andy

    » Harry Rosenthal
    Mo Okt 16, 2017 8:54 am von Andy

    »  BASF-Rückruf - Krebserregender Stoff in Matratzen gelandet?
    Fr Okt 13, 2017 9:51 pm von checker

    » Kasseler Schallkanone soll Angreifer abschrecken
    Do Okt 12, 2017 10:14 pm von Andy

    » *** Radon ***
    Do Okt 12, 2017 10:00 pm von Andy

    » Die Froschfische
    Do Okt 12, 2017 9:54 pm von Andy

    » Der Sternmull
    Do Okt 12, 2017 9:46 pm von Andy

    Navigation
     Portal
     Index
     Mitglieder
     Profil
     FAQ
     Suchen
    Partner
    free forum
    Oktober 2017
    MoDiMiDoFrSaSo
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     

    Kalender Kalender


    Das Erfüllbarkeitsproblem der Aussagenlogik (SAT)

    Vorheriges Thema anzeigen Nächstes Thema anzeigen Nach unten

    Das Erfüllbarkeitsproblem der Aussagenlogik (SAT)

    Beitrag  checker am So Sep 06, 2015 8:58 am

    Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von englisch satisfiability ‚Erfüllbarkeit‘) ist ein Entscheidungsproblem. Es fragt, ob eine aussagenlogische Formel erfüllbar ist. Anwendungen finden sich unter anderem in der Komplexitätstheorie, Verifikation und im Entwurf von logischen Schaltungen. Insbesondere in der Komplexitätstheorie wird mit SAT auch nur der Spezialfall von Formeln bezeichnet, die in konjunktiver Normalform vorliegen.

    Das Erfüllbarkeitsproblem der Aussagenlogik ist in exponentieller Zeit in der Anzahl der Variablen entscheidbar, zum Beispiel durch das Aufstellen einer Wahrheitstabelle. Ob es auch einen Algorithmus gibt, der SAT in Polynomialzeit löst, ist nicht bekannt. Die Forschung beschäftigt sich mit der Entwicklung möglichst effizienter Verfahren (sogenannter SAT-Solver). Bekannte SAT-Solver sind Binäre Entscheidungsdiagramme, oder das Davis-Putnam-Verfahren. Manche Solver verwenden stochastische oder systematische Suchverfahren zur Entscheidung der Erfüllbarkeit. Das bekannteste und am meisten verbreitete Verfahren zur systematischen Suche ist (Stand: 2008) das DPLL-Verfahren (Davis-Putnam-Logemann-Loveland), welches in den letzten Jahrzehnten mit Hilfe von Heuristiken und Lernverfahren stark verbessert wurde.

    SAT gehört zur Klasse \mathcal{NP} der Probleme, die in polynomieller Zeit mit einer nichtdeterministischen Turingmaschine gelöst werden können. Die noch ungelöste Frage, ob SAT auch mit einer deterministischen Turingmaschine (also mit einem herkömmlichen Rechner) in polynomieller Zeit gelöst werden kann, kann man formulieren als: Gilt \mbox{SAT} \in \mathcal{P}?

    Das Erfüllbarkeitsproblem der Aussagenlogik ist NP-vollständig. Das besagt, dass jedes Problem aus \mathcal{NP} in polynomieller Zeit auf SAT zurückgeführt werden kann (Polynomialzeitreduktion). Anfang der 1970er Jahre zeigten Stephen A. Cook und Leonid Levin unabhängig voneinander diese Eigenschaft, bekannt als der Satz von Cook. Cook zeigte hierfür einen Algorithmus auf, mit dem die Berechnungsschritte einer nicht-deterministischen Turingmaschine in Aussagenlogik formuliert und damit auf SAT reduziert werden können. Richard M. Karp zeigte 1972 die NP-Vollständigkeit weiterer Probleme. Er prägte damit das heutige Verständnis von NP-Vollständigkeit.

    Falls also \mbox{SAT} \in \mathcal{P} gilt, dann ist jedes Problem aus \mathcal{NP} auch in \mathcal{P}, das heißt, dann gilt \mathcal{P} = \mathcal{NP}. Auch die umgekehrte Richtung der Implikation gilt. Das P-NP-Problem „gilt \mathcal{P} = \mathcal{NP} oder nicht?“ ist eine der großen ungelösten Fragen der Komplexitätstheorie. Ist ein Problem NP-vollständig, so darf man annehmen, dass die Suche nach einem Polynomialzeit-Algorithmus dafür aussichtslos ist. Diese Annahme entspricht der Überzeugung vieler Mathematiker, dass \mathcal{P} = \mathcal{NP} nicht gilt.

    Varianten von SAT

    SAT kann auf viele Weisen durch Einschränkungen und Verallgemeinerungen variiert werden. Das Problem 3-SAT ist eine Variante, die höchstens drei Literale pro Klausel enthält. Trotz der Einschränkung ist auch 3-SAT NP-vollständig, denn SAT lässt sich in polynomieller Zeit auf 3-SAT reduzieren.

    Jedes 3-SAT mit p Variablen und q Klauseln lässt sich auf einen Graphen G mit p+q Knoten abbilden, in dem alle Variablenknoten mit denjenigen Klauselknoten verbunden sind, in denen sie vorkommen. Eine Formel ist in P3SAT, wenn sie in 3-SAT ist, und der Graph planar ist. Auch P3SAT ist NP-vollständig.

    Das Problem MAX-SAT besteht darin, die maximale Anzahl erfüllbarer Klauseln einer Formel zu bestimmen. Es ist PP-vollständig.[1] MAJ-SAT, das Entscheidungsproblem ob eine aussagenlogische Formel von mehr als der Hälfte aller möglichen Belegungen erfüllt wird, ist ebenfalls PP-vollständig.[1]

    Zu vielen weiteren Komplexitätsklassen gibt es Varianten von SAT, die bezüglich dieser Klassen vollständig sind. Beispielsweise ist die Variante 2-SAT NL-vollständig. Das HORNSAT-Problem ist P-vollständig. Die Erweiterung der aussagenlogischen Formeln durch die Einführung von Quantoren führt zu QBF (auch QSAT genannt), einem PSPACE-vollständigen Problem.

    Schließlich kann man SAT auch mit anderen Entscheidungstheorien koppeln. Das sich ergebende Problem wird als ein SMT-Problem (Satisfiability Modulo Theory) bezeichnet und kann z. B. durch Kodierung in ein reines SAT-Problem oder durch eine Kombination von Entscheidungsverfahren gelöst werden.

    Siehe auch

    Resolution (Logik)
    Circuit Value Problem

    Quelle - literatur & einzelnachweise
    avatar
    checker
    Moderator
    Moderator

    Anzahl der Beiträge : 32509
    Anmeldedatum : 03.04.11
    Ort : Braunschweig

    Benutzerprofil anzeigen

    Nach oben Nach unten

    Vorheriges Thema anzeigen Nächstes Thema anzeigen Nach oben

    - Ähnliche Themen

     
    Befugnisse in diesem Forum
    Sie können in diesem Forum nicht antworten