Boolean satisfiability problem#3-satisfiability

3-SAT is a variant of the satisfiability problem of propositional logic ( satisfiability engl. Satisfiability, short SAT).

It deals with the question of whether present in conjunctive normal form propositional formula containing at most 3 literals per clause is satisfiable. An example of such a formula:

Is now sought an assignment of the variables to 0 or 1, for F the value 1 (true ) assumes. If there is such an assignment, F is satisfiable, otherwise not. As with all NP- complete problems, it is " easy " to check a candidate solution to its validity, in this case to determine whether a given assignment to the variables satisfies the formula. However, the finding of a valid candidate solution is generally " difficult " because no method is known today, to find a satisfying assignment in polynomial time.

All k- SAT problems are NP-complete, 2- SAT is in the complexity class NL, 1- SAT lies in the complexity class L.

The general satisfiability problem of propositional logic (SAT) can be applied to 3-SAT reduction polynomial, and hence is 3- SAT to the set of Cook NP -complete.

3-SAT can be, inter alia, in turn, to the clique problem, the knapsack problem and the directed Hamilton cycle ( DHC ) reduce polynomially, thus these problems are NP-hard as proven.

Variants

Exact 3-SAT

Sometimes it is also required in the definition of 3-SAT, that the clauses contain exactly three literals. This variant of the problem is NP-complete, even if you additionally also requires that all literals are different in a clause.

Max-3 - SAT

This is not required that each clause is true, but as many as possible. Already a random assignment of the variables provides the expectation that 7 /8 of the clauses are satisfied ( because the probability that a particular clause is not satisfied, is only ( 1/2) ^ 3 - assuming that literals not more than once in a clause occur ). The consequence of this is that each such 3- SAT problem, with less than 8 clauses is satisfiable. Max-3 - SAT is also NP- complete since the reduction to the normal 3-SAT is only to ask whether the total number of clauses can be satisfied.

Not - All- Equal - 3-SAT

It is 3-SAT, but only one assignment is accepted, the causes in each clause at least one false and one true literal. Not - All- Equal - 3-SAT is also NP -complete.