Variationen von SAT

14

Ich habe im Internet nachgeschlagen, aber ich konnte keine "große Liste" von Varianten des SAT-Problems finden.

Abgesehen von den (gemeinsamen)

  • SAT,
  • k-SAT,
  • MAX-kSAT,
  • Halb-SAT,
  • XOR-SAT,
  • NAE-SAT

Welche weiteren Varianten gibt es?

(Auch ist es sehr nützlich, wenn dort Komplexitätsklassen angegeben werden (wo möglich))

Subhayan
quelle
Was wäre der Zweck dieser Liste?
Tyson Williams
2
Erstens, weil ich einigen Studenten einen Vortrag halten wollte. Ich hatte vor, über die Variationen von SAT zu sprechen und einige (nicht triviale) Reduktionen zu zeigen. Sie hatten bereits einen Einführungskurs in TOC, daher dachte ich, dass dies eine gute Idee sein könnte es gibt keine solche liste im internet, diese liste richtet sich auch an neugierige, die etwas über die varianten wissen wollen.
Subhayan
11
Ich bin nicht sicher, wie diese Liste bei Ihrem Vortrag helfen wird. Anstatt eine willkürlich lange Liste von SAT-Varianten zu lesen, sollte ein Neugieriger Schäfers Dichotomiesatz und die Verallgemeinerung von Allender et al. Lesen . das zeigt, dass jede mögliche SAT-Variante für eine von sechs bekannten Komplexitätsklassen vollständig ist.
Tyson Williams
das ist ein netter vorschlag ... danke @TysonWilliams .. du kannst das auch zu einer antwort machen, obwohl das nicht genau das ist, wonach ich gesucht habe, aber das ist sicherlich hilfreich.
Subhayan

Antworten:

17

(Kommentieren Sie eine Antwort wie gewünscht und erweitern Sie sie ein wenig.)

"Ein neugieriger Geist" sollte Schäfers Dichotomiesatz und die Verallgemeinerung von Allender et al. das zeigt, dass jede mögliche SAT-Variante entweder trivial oder in einer von sechs bekannten Komplexitätsklassen ist:

  1. NP-vollständig
  2. P-vollständig
  3. NL-komplett
  4. L-komplett
  5. ⊕L-vollständig
  6. Co-NLOGTIME
Tyson Williams
quelle
17

Diese Liste wird sehr lang sein;) Hier sind einige meiner bevorzugten (NP-vollständigen) Varianten von SAT:

  • PLANAR ( 3,3

    Siehe: Dahlhaus, Johnson, Papadimitriou, Seymour, Yannakakis, Die Komplexität von Schnitten mit mehreren Anschlüssen, SIAM Journal of Computing 23 (1994) 864-894

  • 4-BOUNDED PLANAR 3-CONNECTED 3SAT (jede Klausel enthält genau 3 verschiedene Variablen, jede Variable erscheint in höchstens 4 Klauseln, der Bipatit-Incident-Graph ist planar und 3-verbunden)

    Siehe: Kratochvíl, Ein spezielles planares Erfüllbarkeitsproblem und eine Folge seiner NP-Vollständigkeit, Discrete Applied Math. 52 (1994) 233 & ndash; 252

  • MONOTONE CUBIC 1-IN-3SAT (MONOTONE-1-IN-3SAT, in dem jede Variable genau dreimal vorkommt)

    Siehe: Moore und Robsen, Problem mit harten Fliesen mit einfachen Fliesen, Discrete Compute. Geom. 26 (2001) 573-590

  • Finde ich sehr interessant , dass PLANAR-NAE- SAT für jeden in P kkk .

    Siehe diesen Beitrag .

user13136
quelle
4
Wenn Sie den letzten Punkt interessant finden, könnte es Sie auch interessieren zu wissen, dass # PLANAR-NAE-3SAT (Zähllösungen) auch nachvollziehbar ist, während andere scheinbar einfache SAT-Varianten wie PLANAR-MONOTONE-2SAT nachvollziehbar (oder sogar trivial) sind. als Entscheidungsproblem, aber # P-schwer zum Zählen. Beachten Sie, dass die Reduzierung vom letzten Link oben (Reduzierung von PLANAR-NAE-kSAT auf PLANAR-NAE-3SAT) nicht sparsam ist und dass # PLANAR-NAE-4SAT # P-hart ist.
William Whistler
11

Auf der "NP-vollständigen Seite" bin ich auf diese Varianten gestoßen (eine ähnliche Frage habe ich auch bei cs.stackexchange gestellt):

Marzio De Biasi
quelle
7

SEINT(k)SEINTkSEINT(2)LSEINT(k)k3

Jan Johannsen
quelle
1

Neben der obigen Liste gibt es auch:

  • #SAT: Modellzählung
  • All-SAT: Modellaufzählung
qsp
quelle
1

Es gibt eine sehr klassische Verbindung zwischen Logik und Algebra, die auf den Ursprung der modernen Logik und die Arbeit von George Boole zurückgeht. Eine Formel in der Aussagenlogik kann als Element einer Booleschen Algebra interpretiert werden. Die logischen Konstanten wahr und falsch werden zu den algebraischen Begriffen des oberen und unteren Elements eines Gitters. Die logischen Operationen von Konjunktion, Disjunktion und Negation werden zu den algebraischen Operationen von Treffen, Verbinden und Komplementieren in der Booleschen Algebra. Dieser Zusammenhang wird in der modernen Behandlung der Logik weniger betont, ist aber im Zusammenhang mit Ihrer Frage besonders interessant. Mit der Algebra können wir uns von vielen problemspezifischen Details entfernen und Verallgemeinerungen eines Problems finden, die auf viele verschiedene Situationen zutreffen.

Im speziellen Fall von SAT ist die algebraische Frage, was passiert, wenn wir Formeln in allgemeineren Gittern als Booleschen Algebren interpretieren. Auf der logischen Seite können Sie das Erfüllbarkeitsproblem von Aussagenlogik auf intuitionistische Logik verallgemeinern. Allgemeiner können Sie das Problem der Aussagenerfüllbarkeit dahingehend verallgemeinern, dass bestimmt wird, ob eine Formel, wenn sie über ein begrenztes Gitter (eine mit oben und unten) interpretiert wird, das untere Element des Gitters definiert. Mit dieser Verallgemeinerung können Sie Probleme in der Programmanalyse als Erfüllbarkeitsprobleme behandeln.

Eine andere Verallgemeinerung ist die quantifiziererfreie Logik erster Ordnung, bei der die Frage nach dem Erfüllbarkeitsmodul einer Theorie gestellt wird. Das heißt, Sie haben nicht nur boolesche Variablen, sondern auch Variablen erster Ordnung und Funktionssymbole und möchten wissen, ob eine Formel erfüllt werden kann. An dieser Stelle können Sie Fragen zu Formeln in der Arithmetik, zu Stringtheorien oder zu Arrays usw. stellen. So erhalten wir eine strenge und sehr nützliche Verallgemeinerung von SAT, die viele Anwendungen in den Bereichen Systeme, Computersicherheit, Programmiersprachen, Programmüberprüfung und Planung bietet , künstliche Intelligenz usw.

Vijay D
quelle