computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

, not-all-equal 3-satisfiability (NAE3SAT) is an NP-complete variant of the Boolean satisfiability problem, often used in proofs of NP-completeness.

Definition

3-satisfiability In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

, an instance of the problem consists of a collection of Boolean variables and a collection of clauses, each of which combines three variables or negations of variables. However, unlike 3-satisfiability, which requires each clause to have at least one true Boolean value, NAE3SAT requires that the three values in each clause are not all equal to each other (in other words, at least one is true, and at least one is false).

Hardness

The NP-completeness of NAE3SAT can be proven by a reduction from 3-satisfiability (3SAT). First the nonsymmetric 3SAT is reduced to the symmetric NAE4SAT by adding a common dummy literal

s

to every clause, then NAE4SAT is reduced to NAE3SAT by splitting clauses as in the reduction of general

k

-satisfiability to 3SAT. In more detail, a 3SAT instance

\Phi = \bigwedge_^m (l_ \vee l_ \vee l_)

(where the

l_

are arbitrary literals) is reduced to the NAE4SAT instance

\Psi = \bigwedge_^m (l_, l_, l_, s)

where

s

is a new variable. A satisfying assignment for

\Phi

becomes a satisfying assignment for

\Psi

by setting

s = 0

. Conversely a satisfying assignment with

s = 0

for

\Psi

must have at least one other literal true in each clause and thus be a satisfying assignment for

\Phi

. Finally a satisfying assignment with

s = 1

for

\Psi

can because of symmetry of

0

and

1

be flipped to produce a satisfying assignment with

s = 0

. NAE3SAT remains NP-complete when all clauses are monotone (meaning that variables are never negated), by Schaefer's dichotomy theorem. Monotone NAE3SAT can also be interpreted as an instance of the

set splitting problem In computational complexity theory, the set splitting problem is the following decision problem: given a family ''F'' of subsets of a finite set ''S'', decide whether there exists a partition of ''S'' into two subsets ''S1'', ''S2'' such that all e ...

, or as a generalization of graph bipartiteness testing to 3-uniform hypergraphs: it asks whether the vertices of a hypergraph can be colored with two colors so that no hyperedge is monochromatic. More strongly, it is NP-hard to find colorings of 3-uniform hypergraphs with any constant number of colors, even when a 2-coloring exists.

Easy cases

Unlike 3SAT, some variants of NAE3SAT in which graphs representing the structure of variables and clauses are

planar graphs In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

can be solved in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

. In particular this is true when there exists a planar graph with one vertex per variable, one vertex per clause, an edge for each variable-clause incidence, and a cycle of edges connecting all the variable vertices.

References

{{reflist, refs= {{citation , last1 = Dinur , first1 = Irit , author1-link = Irit Dinur , last2 = Regev , first2 = Oded , author2-link = Oded Regev (computer scientist) , last3 = Smyth , first3 = Clifford , issue = 5 , journal = Combinatorica , mr = 2176423 , pages = 519–535 , title = The hardness of 3-uniform hypergraph coloring , volume = 25 , year = 2005 , doi=10.1007/s00493-005-0032-4 {{citation , last = Moret , first = B. M. E. , authorlink = Bernard Moret , date = June 1988 , doi = 10.1145/49097.49099 , issue = 2 , journal = ACM SIGACT News , pages = 51–54 , title = Planar NAE3SAT is in P , volume = 19 {{harvtxt, Moret, 1988: "Among published proofs of NP-completeness, one finds more reductions from 3-Satisfiability (3SAT for short) and its main variants, One- in-three-3SAT (1in3SAT) and Not-all-equal 3SAT (NAE3SAT), than from any other NP-complete problem." {{citation , last1 = Moore , first1 = Cristopher , author1-link = Cristopher Moore , last2 = Mertens , first2 = Stephan , contribution = Symmetry-breaking and NAESAT , contribution-url = https://books.google.com/books?id=z4zMiZyAE1kC&pg=PA133 , isbn = 9780199233212 , pages = 133–138 , publisher = Oxford University Press , title = The Nature of Computation , year = 2011 {{citation , last = Schaefer , first = Thomas J. , authorlink=Thomas Jerome Schaefer , contribution = The complexity of satisfiability problems , location = New York , mr = 521057 , pages = 216–226 , publisher = ACM , title = Proc. Tenth ACM Symposium on Theory of Computing (STOC '78) , year = 1978 NP-complete problems Satisfiability problems