Information About ™One-in-three 3sat |
| CATEGORIES ABOUT ONE-IN-THREE 3SAT | |
| np-complete problems | |
| satisfiability problems | |
|
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 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 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'',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 5''m'' clauses and ''n'' + 6''m'' 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. 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. 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. arXiv:cs.CG/0601002 REFERENCES |
|
|