One-in-three 3SAT

From Wikipedia, the free encyclopedia

One-in-three 3SAT is a variant of 3SAT where the input instance is the same, but the question is to determine whether there exists a satisfying assignment so that exactly one literal in each clause is set to 1 (instead of at least one literal, as in ordinary 3-SAT).

One-in-three 3SAT is listed as NP-complete problem L04 in the standard reference, "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey and Johnson. It was proved to be NP-complete by Thomas J. Schaefer in the proceedings of the 1978 ACM STOC conference, as a special case of Schaefer's Dichotomy Theorem (that any problem generalizing Satisfiability in a certain way is either in the class P or is NP-complete).

Schaefer gives a construction allowing an easy polynomial-time reduction from 3SAT to One-in-three 3SAT. Let "(x or y or z)" be a clause in a 3CNF formula. Add six new boolean variables a, b, c, d, e, and f, to be used to simulate this clause and no other. Let R(u,v,w) be a predicate that is true if and only if exactly one of the booleans u, v, and w are true. Then the formula "R(x,a,d) and R(y,b,d) and R(a,b,e) and R(c,d,f) and R(z,c,0)" is satisfiable by some setting of the new variables if and only if at least one of x, y, or z is true. We may thus convert any 3SAT instance with m clauses and n variables into a One-in-three 3SAT instance with 5m clauses and n+6m variables.

The One-in-three 3SAT problem is often used in the literature as a known NP-complete problem in a reduction to show other problems NP-complete.

The monotone version of the problem, where each clause contains only positive literals, remains NP-complete. Also, if we think of the instance as a graph, with a vertex for each variable and each clause, and an edge connecting a variable to a clause if it occurs (positively or negatively) in that clause, then the problem remains NP-Complete even if the graph is planar.