Classificazione delle intrattabile problema soddisfacibilit'a / trattabili varianti

Question

Recentemente ho trovato in un articolo [1] una versione speciale simmetrica della SAT chiamato il 2/2/4-SAT . Ma ci sono molti $ \ text {} NP $ - varianti complete là fuori, per esempio: MONOCOLORE NAE-3SAT , MONOCOLORE 1-IN-3SAT , .. .

Alcune altre varianti sono trattabili: $ 2 $ - $ \ text {} SAT $, Planar-NAE - $ \ text {} SAT $, ...

Ci sono documenti di indagine (o pagine web) che classificano tutti il ??(strano) $ \ text {SAT} $ varianti che sono state dimostrato di essere $ \ text {NP} $ - completa o in $ \ text ({P } $)?

---

1. trovare una soluzione più breve per il $ N $ x $ N $ estensione della 15-Puzzle è intrattabile da D. Ratner e M. Warmuth (1986)

Answer 1

Classic, i risultati ben noti

Come menzionato da Standa Zivny sulla relativa questione di CSTheory, problemi che SAT sono facili ? , c'è un risultato ben noto da Schaefer dal 1978 (citando la risposta di Zivny):

Se SAT è parametrizzato da un insieme di relazioni consentite in qualsiasi istanza, quindi ci sono solo 6 casi trattabili: 2-SAT (cioè ogni clausola è binario), Horn-SAT, dual-Horn-SAT, affine-SAT ( soluzioni di equazioni lineari in GF (2)), 0-validi (relazioni soddisfatti con l'assegnazione all-0) e 1-validi (relazioni soddisfatti con l'assegnazione all-1).

Planar-3SAT che significa la versione planare di 3SAT è noto per essere \ mathcal {NP} $ $ - completa. Vedere D Lichtenstein, formule Planar ed i loro usi, 1981 . La versione non-planare di 3SAT è, naturalmente, il notissimo $ classico \ mathcal {NP} $ -. Problema completo

Non-All-Equal 3SAT ( NAE-3SAT ) è di $ \ {mathcal NP} $ - completa. Tuttavia, la versione planare di esso è in $ \ mathcal {P} $, come mostrato da Moret, Planar NAE3SAT è in P, 1988 .

più recente e / o "strano" varianti

$ k $ -colourable Monotono NAE-3SAT

Ecco una variante più esotico o strano, un problema decisionale chiamato il $ k $ -colourable Monotono NAE-3SAT :

Dato un monotono CNF espressione $ \ phi $ con esattamente tre variabili distinte in ogni clausola, tale che il corrispondente grafico vincolo $ G (\ phi) $ è k-colorabile, è l'espressione $ \ phi $ non-all uguale satisfiable?

Qui il corrispondente grafico vincolo $ G (\ phi) $ è una semplice grafo non orientato associata con $ \ phi $ come segue: Ogni variabile di $ \ phi $ è un vertice in $ G $, e due vertici avere un vantaggio tra di loro se e solo se essi appaiono in qualche clausola insieme.

Per $ k = 4 $ il problema è nella $ \ mathcal {P} $. Per $ k = 5 $ però, è di $ \ {mathcal NP} $ - completa. Vedere P Jain, su una variante di Monotono NAE-3SAT e il problema Triangolo-Free Cut, 2010 .

lineare CNF varianti

Pur non forse essere insolito o strano, alcune varianti noti, ossia NAE-SAT (non-all-uguali SAT) e XSAT (SAT esatta; < em> esattamente un letterale in ogni clausola a 1 e tutti gli altri letterali a 0), il problema della soddisfacibilità sono stati studiati nel> impostazione linear

NAE-SAT e XSAT rimanere $ \ {mathcal NP} $ - completo quando limitato a formule lineari. Inoltre, NAE-SAT e XSAT sono ancora $ \ mathcal {NP} $ - completa su formule che contengono solo clausole di lunghezza almeno $ k $, per ogni intero positivo fisso $ k \ geq 3 $. Sono $ \ {mathcal NP} $ - completo per monotone (nessun letterali positivi) lineari formule. Tuttavia, NAE-SAT è polinomiale decidibile proseguimento lineari esatte, in cui ogni coppia di clausole distinte contiene esattamente una variabile in comune.

Alcuni ulteriori aspetti relativi alla complessità del NAE-SAT e XSAT , in determinate ipotesi sono probabilmente ancora aperti. Per maggiori dettagli, si veda ad esempio Porschen e Schmidt, in alcune varianti SAT-over lineare formule, 2009 e Porschen et al., Risultati Complessità Linear XSAT-Problemi 2010 .