Classification des variantes de problèmes de satisfiabilité insolubles / tractables

20

Récemment, j'ai trouvé dans un article [1] une version symétrique spéciale de SAT appelée 2/2/4-SAT . Mais il existe de nombreuses variantes complètes, par exemple: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...NP

Quelques autres variantes sont traitables: - , Planar-NAE- , ...SAT SAT2SATSAT

Existe-t-il des documents d'enquête (ou des pages Web) qui classent toutes les variantes (étranges) qui se sont avérées être -complètes (ou dans )?NP PSATNPP


  1. Trouver une solution la plus courte pour l' extension x du 15-Puzzle est intraitableNN par D. Ratner et M. Warmuth (1986)
Vor
la source
@mrm: merci, je ne connaissais pas l'article de Schaefer ( dl.acm.org/citation.cfm?doid=800133.804350 )
Vor
1
J'ai supprimé "poster votre favori", car il s'agit d' un exemple de manuel de ce qu'il ne faut pas demander sur Stack Exchange . (Oui, cela fonctionne dans une certaine mesure sur l' informatique théorique , mais c'est un cas particulier en raison du public très atypique.)
Gilles 'SO- arrête d'être mauvais'

Réponses:

18

Des résultats classiques et 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 de Schaefer de 1978 (citant la réponse de Zivny):

Si SAT est paramétré par un ensemble de relations autorisées dans n'importe quelle instance, alors il n'y a que 6 cas traitables: 2-SAT (c'est-à-dire que chaque clause est binaire), Horn-SAT, dual-Horn-SAT, affine-SAT (solutions à linéaire équations dans GF (2)), 0-valide (relations satisfaites par l'affectation tout-0) et 1-valide (relations satisfaites par l'affectation tout-1).

Planar-3SAT, ce qui signifie que la version planaire de 3SAT est connue pour être complète. Voir D Lichtenstein, Formules planaires et leurs utilisations, 1981 . La version non planaire de 3SAT est bien sûr le problème classique très connu de N P.NPNP

Pas tous égaux 3SAT ( NAE-3SAT ) est complet. Cependant, la version planaire est en P comme le montre Moret, Planar NAE3SAT est en P, 1988 .NPP

Variantes plus récentes et / ou "bizarres"

Monotone k- colorable NAE-3SATk

Voici une variante plus exotique ou bizarre, un problème de décision appelé le colorable Monotone NAE-3SATk :

Étant donné une expression CNF monotone avec exactement trois variables distinctes dans chaque clause, de telle sorte que le graphe de contraintes correspondant G ( ϕ ) est k-colorable, l'expression ϕ n'est-elle pas toutes égales satisfaisante?ϕg(ϕ)ϕ

g(ϕ)ϕϕg

k=4Pk=5NP

Variantes CNF linéaires

Bien que n'étant peut-être pas exotiques ou étranges, certaines variantes bien connues, à savoir NAE-SAT ( SAT pas toutes égales) et XSAT (SAT exact; exactement un littéral dans chaque clause à 1 et tous les autres littéraux à 0), du Le problème de satisfiabilité a été étudié dans le cadre linéaire . Les clauses d'une formule linéaire par paire ont au plus une variable en commun. Fait intéressant, le statut de complexité ne découle pas du théorème de Schaefer.

NPNPkk3NP

Certains autres aspects concernant la complexité de NAE-SAT et XSAT sous certaines hypothèses sont probablement encore ouverts. Pour plus de détails, voir par exemple Porschen et Schmidt, On Some SAT-Variants over Linear Formulas, 2009 et Porschen et al., Complexity Results for Linear XSAT-Problems, 2010 .

Juho
la source