Klassifizierung von unlösbaren/verfolgbaren Erfüllbarkeitsproblemvarianten

Question

Kürzlich fand ich in einem Papier [1] eine spezielle symmetrische Version von SAT The the the 2/2/4-sa. Es gibt jedoch viele $ text {np} $-komplette Varianten da draußen, zum Beispiel: Monotone nae-3sat, Monoton 1-in-3-sa, ...

Einige andere Varianten sind nachvollziehbar: $ 2 $-$ text {sat} $, planar-nae-$ text {sat} $, ...

Gibt es Umfragepapiere (oder Webseiten), die alle (seltsam) $ text {sat} $ varianten klassifizieren, die sich als $ text {np} $-vollständig (oder in $ text {p} $) erwiesen haben ?

---

1. Eine kürzeste Lösung für die Erweiterung $ n $ x $ n $ des 15-Puzzers ist unlösbar von D. Ratner und M. Warmuth (1986)

Answer 1

Klassische, bekannte Ergebnisse

Wie von Standa Zivny über die damit verbundene Frage von CStheory erwähnt, Welche SAT -Probleme sind einfach?, Es gibt ein bekanntes Ergebnis von Schäfer von 1978 (zitieren die Antwort von Zivny):

Wenn SAT durch eine Reihe von Beziehungen parametriert wird, die in einem in keiner Fall zugelassenen Beziehungen zulässig sind, gibt es nur 6 erfolgbare Fälle: 2-sa (dh jede Klausel ist binär), Hornsa, Dual-Horn-Sa, affine-sat (Lösungen für linear Gleichungen in GF(2)), 0-Valid (Beziehungen, die durch die All-0-Zuordnung erfüllt sind) und 1-Valid (Beziehungen, die durch die All-1-Zuordnung erfüllt).

Planar-3sat bedeutet die planare Version von 3sat Es ist bekannt, dass $ mathcal {np} $-vollständig ist. Sehen D Lichtenstein, planare Formeln und ihre Verwendung, 1981. Die nicht planare Version von 3SAT ist natürlich das sehr bekannte klassische $ mathcal {np} $-vollständiges Problem.

Nicht alle gleiche 3SAT (Nae-3sat) ist $ mathcal {np} $-vollständig. Die planare Version davon ist jedoch in $ mathcal {p} $, wie nach gezeigt von Moret, Planar Nae3sat ist in S. 1988.

Neuere und/oder "seltsame" Varianten

$ k $ -Colourable monotone nae-3sat

Hier ist eine exotischere oder seltsamere Variante, ein Entscheidungsproblem namens das $ k $ -Colourable monotone nae-3sat:

Bei einem monoton CNF-Ausdruck $ phi $ mit genau drei unterschiedlichen Variablen in jeder Klausel, so dass der entsprechende Einschränkungsgraf $ g ( phi) $ k-farblich ist, ist der Ausdruck $ phi $ nicht-gar nicht gleichermaßen?

Hier ist der entsprechende Einschränkungsgraphen $ g ( phi) $ ein einfacher, ungerichteter Diagramm, der $ phi $ wie folgt verbunden ist: Jede Variable von $ phi $ ist ein Scheitelpunkt in $ g $, und zwei Scheitelpunkte haben eine Kante zwischen ihnen IFF. Sie erscheinen zusammen in einer Klausel.

Für $ k = 4 $ ist das Problem in $ mathcal {p} $. Für $ k = 5 $ ist es jedoch $ mathcal {np} $-vollständig. Sehen P Jain, auf einer Variante von monotone Nae-3SAT und dem Dreieck-freien Cut-Problem, 2010.

Lineare CNF -Varianten

Obwohl es vielleicht nicht exotisch oder seltsam ist, einige bekannte Varianten, nämlich Nae-sa (nicht alle gleiche SAT) und Xsat (Exakt SAT; genau eins In jeder Klausel zu 1 und allen anderen Literalen bis 0) wurden in der Befriedigungsprobleme untersucht linear Einstellung. Klauseln einer linearen Formel paarweise haben höchstens eine Variable gemeinsam. Interessanterweise folgt der Komplexitätsstatus nicht aus Schaefers Theorem.

Nae-sa und Xsat Bleiben Sie $ mathcal {np} $-vollständig, wenn es auf lineare Formeln beschränkt ist. Darüber hinaus, Nae-sa und Xsat sind immer noch $ mathcal {np} $-vollständige Formeln, die nur Klauseln von Länge enthalten, mindestens $ k $, für jede positive feste Ganzzahl $ k geq 3 $. Sie sind $ mathcal {np} $-vollständig für monotone (keine positiven Literale) lineare Formeln. Jedoch, Nae-sa ist polynomiale Zeit, die auf exakten linearen Formeln enttäuscht werden, wobei jedes Paar verschiedener Klauseln genau eine Variable gemeinsam hat.

Einige weitere Aspekte in Bezug auf die Komplexität von Nae-sa und Xsat Unter bestimmten Annahmen sind wahrscheinlich noch offen. Weitere Einzelheiten finden Sie zum Beispiel Porschen und Schmidt, auf einigen Sat-Varianten über lineare Formeln, 2009 und Porschen et al., Komplexitätsergebnisse für lineare XSAT-Probleme, 2010.