One-in-three 3SAT

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. 

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Three Mile Island — f1 Kernkraftwerk Three Mile Island Kernkraftwerk von Three Mile Island, in dem es 1979 zur Kernschmelze kam …   Deutsch Wikipedia

  • Boolean satisfiability problem — For the concept in mathematical logic, see Satisfiability. 3SAT redirects here. For the Central European television network, see 3sat. In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… …   Wikipédia en Français

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

  • Liste de problèmes np-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Minimum-weight triangulation — In computational geometry and computer science, the minimum weight triangulation (MWT) problem is the problem of finding a triangulation of minimal weight. Of particular interest is the problem of finding a minimum weight point set triangulation …   Wikipedia

  • 2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… …   Wikipedia

  • Stewart Copeland — Copeland am Schlagzeug Stewart Armstrong Copeland (* 16. Juli 1952 in Alexandria, Virginia) ist ein US amerikanischer Schlagzeuger und Komponist. Er hat zu rund 60 Spielfilmen und Fernsehserien die Filmmusik komponiert – allgemein am bekanntesten …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”