Not-all-equal 3-satisfiability
In computational complexity, not-all-equal 3-satisfiability is an NP-complete variant of the Boolean satisfiability problem, often used in proofs of NP-completeness.
Definition
Like 3-satisfiability, 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.Hardness
The NP-completeness of NAE3SAT can be proven by a reduction from 3-satisfiability. First the nonsymmetric 3SAT is reduced to the symmetric NAE4SAT by adding a common dummy literal to every clause, then NAE4SAT is reduced to NAE3SAT by splitting clauses as in the reduction of general -satisfiability to 3SAT.In more detail, a 3SAT instance is reduced to the NAE4SAT instance where is a new variable. A satisfying assignment for becomes a satisfying assignment for by setting. Conversely a satisfying assignment with for must have at least one other literal true in each clause and thus be a satisfying assignment for. Finally a satisfying assignment with for can because of symmetry of and be flipped to produce a satisfying assignment with.
NAE3SAT remains NP-complete when all clauses are monotone, by Schaefer's dichotomy theorem.
Monotone NAE3SAT can also be interpreted as an instance of the set splitting problem, 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.