In computer science, the Boolean Satisfiability Problem is the problem of
determining if there exists an interpretation that satisfies a given
Boolean formula. In other words, it asks whether the variables of a given Boolean
formula can be consistently replaced by the values TRUE or FALSE in such a way
that the formula evaluates to TRUE. If this is the case, the formula is called
satisfiable. On the other hand, if no such assignment exists, the function
expressed by the formula is identically FALSE for all possible variable
assignments and the formula is unsatisfiable. For example, the formula
"a AND NOT b" is satisfiable because one can find the values a = TRUE and b =
FALSE, which make = TRUE. In contrast, "a AND NOT a" is unsatisfiable.
SAT is one of the first problems that was proven to be NP-complete. This means
that all problems in the complexity class NP, which includes a wide range of
natural decision and optimization problems, are at most as difficult to
solve as SAT. There is no known algorithm that efficiently solves SAT,
and it is generally believed that no such algorithm exists; yet this belief
has not been proven mathematically, and resolving the question whether SAT has
an efficient algorithm is equivalent to the P versus NP problem, which is the
most famous open problem in the theory of computing.
Despite the fact that no algorithms are known that solve SAT efficiently,
correctly, and for all possible input instances, many instances of SAT that
occur in practice, such as in artificial intelligence, circuit design and
automatic theorem proving, can actually be solved rather efficiently using
heuristical SAT-solvers. Such algorithms are not believed to be efficient on all
SAT instances, but experimentally these algorithms tend to work well for many
practical applications. Basic definitions and terminology
A propositional logic formula, also called Boolean expression, is built from
variables, operators AND, OR, NOT, and parentheses. A formula is said to be
satisfiable if it can be made TRUE by assigning appropriate logical values to
its variables. The Boolean satisfiability problem is, given a
formula, to check whether it is satisfiable. This decision problem is of
central importance in various areas of computer science, including theoretical
computer science, complexity theory, algorithmics, cryptography and
artificial intelligence. There are several special cases of the
Boolean satisfiability problem in which the formulas are required to have a
particular structure. A literal is either a variable, then called positive
literal, or the negation of a variable, then called negative literal. A clause
is a disjunction of literals. A clause is called Horn clause if it contains at
most one positive literal. A formula is in conjunctive normal form if it is a
conjunction of clauses. For example, "x1" is a positive literal, "¬x2" is a
negative literal, "x1 ∨ ¬x2" is a clause, and "(x1 ∨ ¬x2) ∧ ∧ ¬x1" is a
formula in conjunctive normal form, its 1st and 3rd clause are Horn clauses, but
its 2nd clause is not. The formula is satisfiable, choosing x1=FALSE,
x2=FALSE, and x3 arbitrarily, since ∧ ∧ ¬FALSE evaluates to ∧ ∧ TRUE, and in
turn to TRUE ∧ TRUE ∧ TRUE. In contrast, the CNF formula a ∧ ¬a, consisting of
two clauses of one literal, is unsatisfiable, since for a=TRUE and
a=FALSE it evaluates to TRUE ∧ ¬TRUE and FALSE ∧ ¬FALSE, respectively.
For some versions of the SAT problem, it is useful to define the notion of a
generalized conjunctive normal form formula, viz. as a conjunction of
arbitrarily many generalized clauses, the latter being of the form
R(l1,...,ln) for some boolean operator R and literals li. Different sets of
allowed boolean operators lead to different problem versions. As an
example, R(¬x,a,b) is a generalized clause, and R(¬x,a,b) ∧ R(b,y,c) ∧
R(c,d,¬z) is a generalized conjunctive normal form. This formula is used below,
with R being the ternary operator that is TRUE just if exactly one of its
arguments is. Using the laws of Boolean algebra, every
propositional logic formula can be transformed into an equivalent
conjunctive normal form, which may, however, be exponentially longer. For
example, transforming the formula ∨ ∨ ... ∨ into conjunctive normal form
yields ∧ ∧ ∧ ∧ ... ∧ ∧ ∧ ∧; while the former is a disjunction of n
conjunctions of 2 variables, the latter consists of 2n clauses of n variables.
Complexity and restricted versions = Unrestricted satisfiability=
SAT was the first known NP-complete problem, as proved by Stephen Cook at
the University of Toronto in 1971 and independently by Leonid Levin at the
National Academy of Sciences in 1973. Until that time, the concept of an
NP-complete problem did not even exist. The proof shows how every decision
problem in the complexity class NP can be reduced to the SAT problem for CNF
formulas, sometimes called CNFSAT. A useful property of Cook's reduction is
that it preserves the number of accepting answers. For example, deciding
whether a given graph has a 3-coloring is another problem in NP; if a graph has
17 valid 3-colorings, the SAT formula produced by the Cook–Levin reduction
will have 17 satisfying assignments. NP-completeness only refers to the
run-time of the worst case instances. Many of the instances that occur in
practical applications can be solved much more quickly. See Algorithms for
solving SAT below. SAT is trivial if the formulas are
restricted to those in disjunctive normal form, that is, they are
disjunction of conjunctions of literals. Such a formula is indeed satisfiable if
and only if at least one of its conjunctions is satisfiable, and a
conjunction is satisfiable if and only if it does not contain both x and NOT x
for some variable x. This can be checked in linear time. Furthermore, if they are
restricted to being in full disjunctive normal form, in which every variable
appears exactly once in every conjunction, they can be checked in
constant time. But it can take exponential time and space to convert a
general SAT problem to disjunctive normal form; for an example exchange "∧"
and "∨" in the above exponential blow-up example for conjunctive normal forms.
= 3-satisfiability= Like the satisfiability problem for
arbitrary formulas, determining the satisfiability of a formula in
conjunctive normal form where each clause is limited to at most three
literals is NP-complete also; this problem is called 3-SAT, 3CNFSAT, or
3-satisfiability. To reduce the unrestricted SAT problem to 3-SAT,
transform each clause "l1 ∨ ... ∨ ln" to a conjunction of n − 2 clauses "(l1 ∨ l2
∨ x2) ∧ ∧ ∧ ... ∧ ∧", where x2,...,xn − 2 are fresh variables not occurring
elsewhere. Although the two formulas are not logically equivalent, they are
equisatisfiable. The formula resulting from transforming all clauses is at most
3 times as long as its original, i.e. the length growth is polynomial.
3-SAT is one of Karp's 21 NP-complete problems, and it is used as a starting
point for proving that other problems are also NP-hard. This is done by
polynomial-time reduction from 3-SAT to the other problem. An example of a
problem where this method has been used is the clique problem: given a CNF
formula consisting of c clauses, the corresponding graph consists of a vertex
for each literal, and an edge between each two non-contradicting literals from
different clauses, cf. picture. The graph has a c-clique if and only if the
formula is satisfiable. There is a simple randomized algorithm
due to Schöning that runs in timen where n is the number of variables in the
3-SAT proposition, and succeeds with high probability to correctly decide
3-SAT. The exponential time hypothesis asserts
that no algorithm can solve 3-SAT in time that is fundamentally faster than
exp(o(n)). Selman, Mitchell, and Levesque give
empirical data on the difficulty of randomly generated 3-SAT formulas,
depending on their size parameters. Difficulty is measured in number
recursive calls made by a DPLL algorithm.
3-satisfiability can be generalized to k-satisfiability, when formulas in CNF
are considered with each clause containing up to k literals. However,
since for any k≥3, this problem can neither be easier than 3-SAT nor harder
than SAT, and the latter two are NP-complete, so must be k-SAT.
Some authors restrict k-SAT to CNF formulas with exactly k literals. This
doesn't lead to a different complexity class either, as each clause "l1 ∨ ... ∨
lj" with j