Ostatnio znalazłem w artykule [1] specjalną symetryczną wersję SAT o nazwie 2/2/4-SAT . Ale istnieje wiele wariantów kompletnych , na przykład: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...$\text{NP}$

Możliwe są inne warianty: - SAT , Planar-NAE- SAT , ...$2$$\text{SAT}$$\text{SAT}$

Czy istnieją artykuły ankietowe (lub strony internetowe), które klasyfikują wszystkie (dziwne) warianty , które okazały się być NP- kompletne (lub w P )?$\text{SAT}$$\text{NP}$$\text{P}$

1. Znalezienie najkrótszego rozwiązania dla rozszerzenia x N 15-puzzle jest niemożliwe$N$$N$ do znalezienia przez D. Ratnera i M. Warmutha (1986)

Klasyczne, dobrze znane wyniki

Jak wspomniała Standa Zivny w pokrewnej kwestii CSTheory, które problemy SAT są łatwe? , jest dobrze znany wynik Schaefera z 1978 r. (cytujący odpowiedź Zivnego):

Jeśli SAT jest sparametryzowany przez zestaw relacji dozwolonych w dowolnym przypadku, wówczas istnieje tylko 6 możliwych do prześledzenia przypadków: 2-SAT (tj. Każda klauzula jest binarna), Horn-SAT, dual-Horn-SAT, affine-SAT (rozwiązania liniowe równania w GF (2)), zero-poprawne (relacje spełnione przez przypisanie all-0) i 1-poprawne (relacje spełnione przez przypisanie all-1).

Planarnie 3SAT czyli płaskiej wersji 3SAT znany jest -Complete. Patrz D. Lichtenstein, Formuły planarne i ich zastosowania, 1981 . Niepłaska wersja 3SAT jest oczywiście dobrze znane klasycznej N P -Complete problemu.$\mathcal{NP}$$\mathcal{NP}$

Nie-All-Równe 3SAT ( NAE-3SAT ) jest -Complete. Jednak jego planarna wersja jest w P, jak pokazuje Moret, Planar NAE3SAT jest w P, 1988 .$\mathcal{NP}$$\mathcal{P}$

Nowsze i / lub „dziwne” warianty

-kolorowa monotonia NAE-3SAT$k$

Oto bardziej egzotyczny lub dziwny wariant, problem decyzyjny zwany kolorową Monotone NAE-3SAT$k$ :

Biorąc pod uwagę monotoniczne wyrażenie CNF z dokładnie trzema odrębnymi zmiennymi w każdej klauzuli, tak że odpowiadający mu wykres ograniczeń G ( ϕ ) jest k-kolorowy, czy wyrażenie ϕ nie jest jednakowo równe zadowalające?$\phi$$G(\phi)$$\phi$

$G(\phi)$$\phi$$\phi$$G$

$k=4$$\mathcal{P}$$k=5$$\mathcal{NP}$

Liniowe warianty CNF

Chociaż być może nie są egzotyczne ani dziwne, niektóre dobrze znane warianty, a mianowicie NAE-SAT ( nierównomiernie SAT) i XSAT (Dokładnie SAT; dokładnie jeden literał w każdej klauzuli na 1 i wszystkie inne literały na 0), problem satysfakcji badano w ustawieniu liniowym . Klauzule formuły liniowej parami mają co najwyżej jedną wspólną cechę. Co ciekawe, status złożoności nie wynika z twierdzenia Schaefera.

$\mathcal{NP}$$\mathcal{NP}$$k$$k \geq 3$$\mathcal{NP}$

Pewne dalsze aspekty dotyczące złożoności NAE-SAT i XSAT przy pewnych założeniach są prawdopodobnie nadal otwarte. Aby uzyskać więcej szczegółów, patrz na przykład Porschen i Schmidt, On Some-Variants over Linear Formulas, 2009 i Porschen i wsp., Complexity Results for Linear XSAT-Problems, 2010 .