Pour quel k est PLANAR NAE k-SAT en P?

Le problème Not All Equal -SAT (NAE k -SAT), étant donné un ensemble C de clauses sur un ensemble X de variables booléennes telles que chaque clause contient au plus k littéraux, demande s'il existe une affectation de vérité des variables telles que chaque clause contient au moins un vrai et au moins un faux littéral.$k$$k$$C$$X$$k$

Le problème PLANAR NAE -SAT est la restriction de NAE k -SAT aux cas où le graphique bipartite d'incidence de C et X (c'est-à-dire le graphique des parties C et X avec une arête entre x ∈ X et c ∈ C si et seulement si x ou ¯ x appartient à c ), est plan.$k$$k$$C$$X$$C$$X$$x\in X$$c\in C$$x$$\overline{x}$$c$

On sait que NAE 3-SAT est NP-complet (Garey et Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness), mais PLANAR NAE 3-SAT est en P (voir Planar NAE3SAT est en P, B Moret, ACM SIGACT News, Volume 19 Numéro 2, été 1988 - malheureusement je n'ai pas accès à cet article).

PLANAR NAE -SAT est-il en P pour certains k ≥ 4 ? Y a-t-il une valeur de k pour laquelle il a été démontré qu'elle est NP-complète?$k$$k\geq 4$$k$

PLANAR NAE -SAT est en P pour toutes les valeurs de k .$k$$k$

La raison en est que nous pouvons réduire PLANAR NAE -SAT à PLANAR NAE 3 -SAT. Soit ϕ une instance de PLANAR NAE k -SAT, et supposons que ϕ contient une clause C avec les littéraux ℓ 1 , ℓ 2 , … , ℓ k . Introduisez une nouvelle variable v C et remplacez C par deux clauses NAE C 1 et C 2 . C 1 contient 3 littéraux ℓ 1 , ℓ $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$et , tandis que C 2 contient k - 1 littéraux ˉ v C , ℓ 3 , ℓ 4 , … , ℓ k . Il est facile de voir que C est satisfiable si C 1 ∧ C 2 l' est et que la transformation préserve la planarité. Maintenant, nous pouvons appliquer à plusieurs reprises cette procédure sur les clauses pour finalement obtenir une instance ϕ ′ de NAE 3 -SAT comme souhaité.$v_C$$C_2$$k-1$$\bar{v}_C, \ell_3, \ell_4, \dots, \ell_k$$C$$C_1 \wedge C_2$$\phi'$$3$