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$ $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$ $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$ $k\geq 4$ $k$

— Florent Foucaud
źródło

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ły $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$ $C_1 \wedge C_2$ $\phi'$ $3$

— arnab
źródło

Świetna odpowiedź. Czy to już było znane?

— Serge Gaspers

Wygląda na to, że ta redukcja „działa” nawet bez warunku planarnego, więc prawdopodobnie jest „znana”

— Suresh Venkat

@ Serge Jestem pewien, że tak, ale nie znam referencji.

— arnab

Jest to standardowa redukcja, która działa również dla „zwykłego” SAT. Można go znaleźć np. W książce Sipsera „Wprowadzenie do teorii obliczeń” i wielu innych.

— 5501