<p>PLANAR NAE $k$-SAT is in P for all values of $k$ . </p>

<p>Reason is that we can reduce PLANAR NAE $k$-SAT to PLANAR NAE $3$-SAT. Let $\phi$ be an instance of PLANAR NAE $k$-SAT, and suppose $\phi$ contains a clause $C$ with literals $\ell_1, \ell_2, \dots, \ell_k$. Introduce a new variable $v_C$, and replace $C$ with two NAE clauses $C_1$ and $C_2$. $C_1$ contains $3$ literals $\ell_1$, $\ell_2$, and $v_C$, while $C_2$ contains $k-1$ literals $\bar{v}_C, \ell_3, \ell_4, \dots, \ell_k$. It's easy to see that $C$ is satisfiable iff $C_1 \wedge C_2$ is and that the transformation preserves planarity. Now, we can repeatedly apply this procedure on the clauses to eventually obtain an instance $\phi&#39;$ of NAE $3$-SAT as desired.</p>

CC BY-SA 3.0
2011-04-11T15:40:12.490Z
Great answer. Was this already known?
Serge Gaspers
CC BY-SA 3.0
2011-04-11T16:07:06.523Z
It sounds like this reduction "works" even without the planar proviso, so it's probably "known"
Suresh Venkat
CC BY-SA 3.0
2011-04-11T16:07:29.073Z
@Serge I'm sure it was, but I don't know of a reference.
arnab
CC BY-SA 3.0
2011-04-11T18:51:01.483Z
It is a standard reduction, which also works for "regular" SAT. You can find it e.g. in Sipser's book "Introduction to the Theory of Computation" and in many more.
5501
CC BY-SA 3.0
2011-04-11T15:12:35.963Z
2011-04-11T15:12:35.963Z
arnab
<p>The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth assignment of the variables such that each clause contains at least one true and at least one false literal.</p>

<p>The PLANAR NAE $k$-SAT problem is the restriction of NAE $k$-SAT to those instances where the incidence bipartite graph of $C$ and $X$ (i.e. the graph of parts $C$ and $X$ with an edge between $x\in X$ and $c\in C$ if and only if $x$ or $\overline{x}$ belongs to $c$), is planar.</p>

<p>It is known that NAE 3-SAT is NP-complete (Garey and Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness), but PLANAR NAE 3-SAT is in P (see <a href="http://dx.doi.org/10.1145/49097.49099">Planar NAE3SAT is in P, B. Moret, ACM SIGACT News, Volume 19 Issue 2, Summer 1988</a> - unfortunately I do not have access to this paper).</p>

<p>Is PLANAR NAE $k$-SAT in P for some $k\geq 4$? Is there a value of $k$ for which it has been shown to be NP-complete?</p>

<cc.complexity-theory><reference-request><np-hardness><polynomial-time>
For which k is PLANAR NAE k-SAT in P?
Florent Foucaud
# For which k is PLANAR NAE k-SAT in P?

(Asked by: username_0 on 2011-04-11)

The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth assignment of the variables such that each clause contains at least one true and at least one false literal.

The PLANAR NAE $k$-SAT problem is the restriction of NAE $k$-SAT to those instances where the incidence bipartite graph of $C$ and $X$ (i.e. the graph of parts $C$ and $X$ with an edge between $x\in X$ and $c\in C$ if and only if $x$ or $\overline{x}$ belongs to $c$), is planar.

It is known that NAE 3-SAT is NP-complete (Garey and Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness), but PLANAR NAE 3-SAT is in P (see [Planar NAE3SAT is in P, B. Moret, ACM SIGACT News, Volume 19 Issue 2, Summer 1988](http://dx.doi.org/10.1145/49097.49099) - unfortunately I do not have access to this paper).

Is PLANAR NAE $k$-SAT in P for some $k\geq 4$? Is there a value of $k$ for which it has been shown to be NP-complete?

**Tags:** cc.complexity-theory, reference-request, np-hardness, polynomial-time

---

## 1 answers

### Answer by username_1 on 2011-04-11. Score: 23 | Accepted answer

PLANAR NAE $k$-SAT is in P for all values of $k$ .

Reason is that we can reduce PLANAR NAE $k$-SAT to PLANAR NAE $3$-SAT. Let $\phi$ be an instance of PLANAR NAE $k$-SAT, and suppose $\phi$ contains a clause $C$ with literals $\ell\_1, \ell\_2, \dots, \ell\_k$. Introduce a new variable $v\_C$, and replace $C$ with two NAE clauses $C\_1$ and $C\_2$. $C\_1$ contains $3$ literals $\ell\_1$, $\ell\_2$, and $v\_C$, while $C\_2$ contains $k-1$ literals $\bar{v}\_C, \ell\_3, \ell\_4, \dots, \ell\_k$. It's easy to see that $C$ is satisfiable iff $C\_1 \wedge C\_2$ is and that the transformation preserves planarity. Now, we can repeatedly apply this procedure on the clauses to eventually obtain an instance $\phi'$ of NAE $3$-SAT as desired.

> **Comments:**
> **username_2**: Great answer. Was this already known?  
> **username_3**: It sounds like this reduction "works" even without the planar proviso, so it's probably "known"  
> **username_1**: @Serge I'm sure it was, but I don't know of a reference.  
> **username_4**: It is a standard reduction, which also works for "regular" SAT. You can find it e.g. in Sipser's book "Introduction to the Theory of Computation" and in many more.  

---

