Dla którego k jest PLANAR NAE k-SAT w P?

Problem nie wszystkie równe SAT (NAE -SAT), biorąc pod uwagę zbiór klauzul nad zestawem zmiennych boolowskich, tak że każda klauzula zawiera co najwyżej literałów, pyta, czy istnieje przyporządkowanie zmiennych do takich wartości, że każda klauzula zawiera co najmniej jeden prawdziwy i co najmniej jeden fałszywy literał.k C X $k$$k$$C$$X$$k$

Problem PLANAR NAE SAT polega na ograniczeniu NAE SAT do przypadków, w których dwustronny wykres występowania i (tj. Wykres części i z krawędzią między i jeśli i tylko jeśli lub należy do ), jest płaski.k C X C X x ∈ X c ∈ C x ¯ x$k$$k$$C$$X$$C$$X$$x\in X$$c\in C$$x$$\overline{x}$$c$

Wiadomo, że NAE 3-SAT jest NP-kompletny (Garey i Johnson, Computers and Intractability; Przewodnik po teorii kompletności NP), ale PLANAR NAE 3-SAT jest w P (patrz Planar NAE3SAT jest w P, B Moret, ACM SIGACT News, tom 19, wydanie 2, lato 1988 - niestety nie mam dostępu do tego artykułu).

Czy PLANAR NAE SAT w P dla niektórych ? Czy istnieje wartość dla której wykazano, że jest NP-kompletna?k ≥ 4 $k$$k\geq 4$$k$

PLANAR NAE SAT jest w P dla wszystkich wartości .$k$$k$

Powodem jest to, że możemy zredukować PLANAR NAE SAT do PLANAR NAE SAT. Niech będzie instancją PLANAR NAE -SAT, i załóżmy, że zawiera klauzulę z literałami . Wprowadź nową zmienną i zamień dwie klauzule NAE i . zawiera literały , i , podczas gdy zawiera literały3 ϕ k ϕ C ℓ 1 , ℓ 2 , … , ℓ k v C C C 1 C 2 C 1 3 ℓ 1 ℓ 2 v C C 2 k - 1 ˉ v C , ℓ 3 , ℓ 4 , … , ℓ $k$$3$$\phi$$k$$\phi$$C$$\ell_1, \ell_2, \dots, \ell_k$$v_C$$C$$C_1$$C_2$$C_1$$3$$\ell_1$$\ell_2$$v_C$$C_2$$k-1$$\bar{v}_C, \ell_3, \ell_4, \dots, \ell_k$ . Łatwo zauważyć, że jest zadowalające, jeśli jest, i że transformacja zachowuje płaskość. Teraz możemy wielokrotnie stosować tę procedurę do klauzul, aby ostatecznie uzyskać instancję NAE SAT według potrzeb.C 1 ∧ C 2 ϕ ′$C$$C_1 \wedge C_2$$\phi'$$3$