Klassifizierung von Varianten des Problems der schwer umsetzbaren / umsetzbaren Erfüllbarkeit

20

Kürzlich habe ich in einer Arbeit [1] eine spezielle symmetrische Version von SAT gefunden, die 2/2/4-SAT genannt wird . Es gibt aber viele vollständige Varianten, zum Beispiel: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...NP

Einige andere Varianten sind möglich: - SAT , Planar-NAE- SAT , ...2SATSAT

Gibt es Umfragepapiere (oder Webseiten), die alle (seltsamen) Varianten klassifizieren , deren NP- Vollständigkeit nachgewiesen wurde (oder in P )?SATNPP


  1. NND. Ratner und M. Warmuth (1986) finden eine kürzeste Lösung für die N x N- Erweiterung des 15-Puzzles.
Vor
quelle
@mrm: Danke, ich kannte Schaefers Artikel nicht ( dl.acm.org/citation.cfm?doid=800133.804350 )
Vor
1
Ich habe "post your favourite" entfernt, da dies ein Lehrbuchbeispiel dafür ist, was Sie bei Stack Exchange nicht fragen sollten . (Ja, es funktioniert in gewissem Umfang auf dem Gebiet der Theoretischen Informatik , aber das ist ein Sonderfall, da das Publikum sehr untypisch ist.)
Gilles 'SO - hör auf, böse zu sein',

Antworten:

18

Klassische, bekannte Ergebnisse

Wie von Standa Zivny zu der verwandten Frage von CSTheory erwähnt, sind welche SAT-Probleme einfach? gibt es ein bekanntes Ergebnis von Schäfer aus dem Jahr 1978 (mit der Antwort von Zivny):

Wenn SAT durch eine Reihe von Beziehungen parametrisiert wird, die in jedem Fall zulässig sind, gibt es nur 6 verfolgbare Fälle: 2-SAT (dh jede Klausel ist binär), Horn-SAT, Dual-Horn-SAT, Affin-SAT (Lösungen zu Linear Gleichungen in GF (2)), 0-gültig (Relationen, die durch die All-0-Zuordnung erfüllt sind) und 1-gültig (Relationen, die durch die All-1-Zuordnung erfüllt sind).

NPNP

NPP

Neuere und / oder "komische" Varianten

k

k

ϕG(ϕ)ϕ

G(ϕ)ϕϕG

k=4Pk=5NP

Lineare CNF-Varianten

Obwohl sie nicht exotisch oder seltsam sind, gibt es einige bekannte Varianten, nämlich NAE-SAT (nicht alle gleich SAT) und XSAT ( genau SAT; genau ein Literal in jedem Satz zu 1 und alle anderen Literale zu 0) Erfüllbarkeitsproblem wurden in der linearen Einstellung untersucht. Sätze einer linearen Formel haben paarweise höchstens eine Variable gemeinsam. Interessanterweise folgt der Komplexitätsstatus nicht aus Schäfers Theorem.

NPNPkk3NP

Einige weitere Aspekte bezüglich der Komplexität von NAE-SAT und XSAT sind unter bestimmten Annahmen wahrscheinlich noch offen. Für weitere Einzelheiten siehe zum Beispiel Porschen und Schmidt, Über einige SAT-Varianten über lineare Formeln, 2009 und Porschen et al., Komplexitätsergebnisse für lineare XSAT-Probleme, 2010 .

Juho
quelle