Boolean satisfiability problem: Difference between revisions

Revision as of 21:51, 6 May 2009

Revision as of 22:17, 6 May 2009

Line 60:

To solve this instance of the decision problem we must determine whether there is a truth value (TRUE or FALSE) we can assign to each of the literals (''x''₁ through ''x''₄) such that the entire expression is TRUE. In this instance, there is such an assignment (''x''₁ = TRUE, ''x''₂ = TRUE, ''x''₃=TRUE, ''x''₄=TRUE), so the answer to this instance is YES. This is one of many possible assignments, with for instance, any set of assignments including ''x''₁ = TRUE being sufficient. If there were no such assignment(s), the answer would be NO.

Since k-SAT (the general case) reduces to 3-SAT{{Fact|date=May 2009}}, and 3-SAT can be proven to be [[NP-complete]], it can be used to prove that other problems are also NP-complete. This is done by showing how a solution to another problem could be used to solve 3-SAT. An example of a problem where this method has been used is "[[Clique problem|Clique]]". It's often easier to use reductions from 3-SAT than SAT to problems that researchers are attempting to prove NP-complete.

3-SAT can be further restricted to [[One-in-three 3SAT]], where we ask if ''exactly'' one of the variables in each clause is true, rather than ''at least'' one. One-in-three 3SAT remains NP-complete.