One-in-three 3SAT

In computational complexity theory, one-in-three 3SAT (also known variously as 1-in-3 SAT and exactly-1 3SAT) is an NP-complete problem. The problem is a variant of the 3-satisfiability problem (3SAT). Like 3SAT, the input instance is a collection of clauses, where each clause consists of exactly three literals, and each literal is either a variable or its negation. The one-in-three 3SAT problem is to determine whether there exists a truth assignment to the variables so that each clause has exactly one true literal (and thus exactly two false literals). (In contrast, ordinary 3SAT requires that every clause has at least one true literal.)

One-in-three 3SAT is listed as NP-complete problem LO4 in the standard reference, Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson. It was proved to be NP-complete by Thomas J. Schaefer as a special case of Schaefer's dichotomy theorem, which asserts that any problem generalizing Boolean satisfiability in a certain way is either in the class P or is NP-complete.^[1]

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 is 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,false)" 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.

Another reduction involves only four new variables and three clauses: $R(\neg x, a, b) \land R(b, y, c) \land R(c, d, \neg z)$.

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

Variations

In monotone one-in-three 3SAT, every literal is simply a variable; in other words, there is no negation. This problem is also NP-complete, as proved by Schaefer.^[1] Indeed, this was the original problem from Schaefer's point of view, which he called ONE-IN-THREE SATISFIABILITY.

We can think of the instance to one-in-three SAT 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. In planar one-in-three 3SAT, this graph is assumed to be planar. This problem is also NP-complete.^[2]

References

1. ^ ^{a b} Schaefer, Thomas J. (1978). "The complexity of satisfiability problems". Proceedings of the 10th Annual ACM Symposium on Theory of Computing. San Diego, California. pp. 216–226. doi:10.1145/800133.804350. 
2. ^ Laroche, Philippe (1993). "Planar 1-in-3 satisfiability is NP-complete". Comptes rendus de l'Académie des sciences. Série 1, Mathématique ISSN 0764-4442. pp. vol. 316, no4, pp. 389-392. http://cat.inist.fr/?aModele=afficheN&cpsidt=3921107.