Classification des problèmes satisfiability intraitable / tractable variantes

Question

Récemment, je trouve dans un document [1] une version spéciale symétrique de SAT appelé le 2/2/4-SAT . Mais il y a beaucoup $ \ texte {NP} $ - variantes complètes là-bas, par exemple: MONOTONE NAE-3SAT , MONOTONE 1-IN-3SAT , .. .

D'autres variantes sont traitables: $ 2 $ - $ text \ {SAT} $, Planar-NAE - $ text \ {SAT} $, ...

Y at-il des documents d'enquête (ou des pages Web) qui classifient tous les (bizarre) texte $ \ {SAT} variantes de $ qui ont été révélés être du texte $ \ {NP} de $ - complet (ou $ \ texte {P } $)?

---

1. trouver une solution la plus courte pour le $ N $ x N $ $ extension du 15-Puzzle est intraitable par D. Ratner et M. Warmuth (1986)

Answer 1

classique, les résultats bien connus

Comme mentionné par Standa Zivny sur la question connexe de CSTheory, Quels problèmes SAT sont faciles , il y a un résultat bien connu par Schaefer de 1978 (citant la réponse de Zivny):

  

Si SAT est paramétré par un ensemble de relations autorisées dans tous les cas, alors il y a seulement 6 cas traitables: 2-SAT (chaque clause est binaire), Horn-SAT, double-Horn-SAT, affines-SAT ( des solutions aux équations linéaires dans GF (2)), 0-valides (relations satisfaites par l'affectation tout-0) et 1-valides (relations satisfaites par l'affectation tout-1).

Planar-3SAT qui signifie que la version plane de 3SAT est connu pour être $ \ mathcal {NP} $ - complète. Voir D Lichtenstein, formules planaires et leurs utilisations, 1981 . La version non plane de 3SAT est bien sûr le très bien connu $ \ mathcal classique {NP} $ -. Problème complet

Non-All-égalité 3SAT ( NAE-3SAT ) est $ \ mathcal {NP} $ - complète. Cependant, la version plane est en $ \ mathcal {P} $ comme indiqué par moret, Planar NAE3SAT est en P, 1988 .

Plus récent et / ou "bizarre" variantes

$ k $ -colourable Monotone NAE-3SAT

Voici une variante plus exotique ou bizarre, un problème de décision appelé $ k $ -colourable Monotone NAE-3SAT :

  

Etant donné un monotone expression CNF $ \ phi $ avec exactement trois variables distinctes dans chaque clause, de sorte que le graphe de contraintes correspondant $ G (\ phi) $ est k-colorable, est l'expression $ \ phi $ non-tout- égale satis?

Voici le graphe de contrainte $ G (\ phi) $ est un simple graphe non orienté correspondant associé à $ \ phi $ comme suit: Chaque variable de $ \ phi $ est un sommet de $ G $, et deux sommets ont un bord entre les IFF ils apparaissent dans une clause ensemble.

Pour $ k = 4 $ le problème est dans $ \ mathcal {P} $. Pour $ k = 5 $ cependant, il est $ \ mathcal {NP} $ - complète. Voir P Jain, sur une variante de Monotone NAE-3SAT et le problème Cut Triangle-gratuit, 2010 .

linéaire CNF variantes

Bien que ne pas être peut-être exotique ou bizarre, quelques variantes bien connues, à savoir NAE-SAT (sans tout égale SAT) et XSAT (Exact SAT; < em> exactement un littéral dans chaque clause à 1 et tous les autres littéraux à 0), du problème de satisfiabilité ont été étudiés dans le linéaire réglage. Les articles d'une paire de formule linéaire ont au plus une variable commune. Fait intéressant, l'état de la complexité ne suit pas du théorème de Schaefer.

NAE-SAT et XSAT restent $ \ mathcal {NP} $ - complet si limité aux formules linéaires. De plus, NAE-SAT et XSAT sont encore $ \ mathcal {NP} $ - complet sur les formules ne contenant que des clauses de longueur au moins k $ $, pour chaque entier fixe positif $ k \ geq 3 $. Ils sont $ \ mathcal {NP} $ - complet pour monotones (pas de littéraux positifs) linéaire formules. Cependant, NAE-SAT est décidable polynomial sur des formules linéaires exactes, où chaque paire de clauses distinctes a exactement une variable en commun.

Certains autres aspects concernant la complexité des NAE-SAT et XSAT sous certaines hypothèses sont probablement encore ouvertes. Pour plus de détails, voir par exemple Porschen et Schmidt, sur certains SAT-variantes sur linéaire Formules 2009 et Porschen et al., Résultats de complexité pour Linear XSAT-problèmes 2010 .