In computer science, the Boolean Satisfiability Problem (sometimes called Propositional Satisfiability Problem and abbreviated as SATISFIABILITY or SAT) 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 (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.
SAT is one of the first problems that was proven to be NPcomplete. 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 SATsolvers. 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 (conjunction, also denoted by ∧), OR (disjunction, ∨), NOT (negation, ¬), and parentheses. A formula is said to be satisfiable if it can be made TRUE by assigning appropriate logical values (i.e. TRUE, FALSE) to its variables. The Boolean satisfiability problem (SAT) 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 (or a single literal). A clause is called Horn clause if it contains at most one positive literal. A formula is in conjunctive normal form (CNF) if it is a conjunction of clauses (or a single clause). For example, "x_{1}" is a positive literal, "¬x_{2}" is a negative literal, "x_{1} ∨ ¬x_{2}" is a clause, and "(x_{1} ∨ ¬x_{2}) ∧ (¬x_{1} ∨ x_{2} ∨ x_{3}) ∧ ¬x_{1}" 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 x_{1}=FALSE, x_{2}=FALSE, and x_{3} arbitrarily, since (FALSE ∨ ¬FALSE) ∧ (¬FALSE ∨ FALSE ∨ x_{3}) ∧ ¬FALSE evaluates to (FALSE ∨ TRUE) ∧ (TRUE ∨ FALSE ∨ x_{3}) ∧ TRUE, and in turn to TRUE ∧ TRUE ∧ TRUE (i.e. to 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 (i.e. to FALSE) and FALSE ∧ ¬FALSE (i.e. again to 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(l_{1},...,l_{n}) for some boolean operator R and (ordinary) literals l_{i}. 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 (x_{1}∧y_{1}) ∨ (x_{2}∧y_{2}) ∨ ... ∨ (x_{n}∧y_{n}) into conjunctive normal form yields (x_{1}∨x_{2}∨…∨x_{n}) ∧ (y_{1}∨x_{2}∨…∨x_{n}) ∧ (x_{1}∨y_{2}∨…∨x_{n}) ∧ (y_{1}∨y_{2}∨…∨x_{n}) ∧ ... ∧ (x_{1}∨x_{2}∨…∨y_{n}) ∧ (y_{1}∨x_{2}∨…∨y_{n}) ∧ (x_{1}∨y_{2}∨…∨y_{n}) ∧ (y_{1}∨y_{2}∨…∨y_{n}); while the former is a disjunction of n conjunctions of 2 variables, the latter consists of 2^{n} clauses of n variables.
Complexity and restricted versions
Unrestricted satisfiability (SAT)
SAT was the first known NPcomplete problem, as proved by Stephen Cook at the University of Toronto in 1971^{[1]} and independently by Leonid Levin at the National Academy of Sciences in 1973.^{[2]} Until that time, the concept of an NPcomplete 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^{[note 1]} 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 3coloring is another problem in NP; if a graph has 17 valid 3colorings, the SAT formula produced by the Cook–Levin reduction will have 17 satisfying assignments.
NPcompleteness only refers to the runtime 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 (each conjunction represents one satisfying assignment). 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 blowup example for conjunctive normal forms.
3satisfiability
The 3SAT instance (
x∨
x∨
y) ∧ (¬
x∨¬
y∨¬
y) ∧ (¬
x∨
y∨
y) reduced to a
clique problem. The green vertices form a 3clique and correspond to the satisfying assignment
x=FALSE,
y=TRUE.
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 NPcomplete also; this problem is called 3SAT, 3CNFSAT, or 3satisfiability. To reduce the unrestricted SAT problem to 3SAT, transform each clause "l_{1} ∨ ... ∨ l_{n}" to a conjunction of n − 2 clauses "(l_{1} ∨ l_{2} ∨ x_{2}) ∧ (¬x_{2} ∨ l_{3} ∨ x_{3}) ∧ (¬x_{3} ∨ l_{4} ∨ x_{4}) ∧ ... ∧ (¬x_{n − 3} ∨ l_{n − 2} ∨ x_{n − 2}) ∧ (¬x_{n − 2} ∨ l_{n − 1} ∨ l_{n})", where x_{2},...,x_{n − 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]}
3SAT is one of Karp's 21 NPcomplete problems, and it is used as a starting point for proving that other problems are also NPhard.^{[note 2]} This is done by polynomialtime reduction from 3SAT 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 noncontradicting^{[note 3]} literals from different clauses, cf. picture. The graph has a cclique if and only if the formula is satisfiable.^{[4]}
There is a simple randomized algorithm due to Schöning (1999) that runs in time (4/3)^{n} where n is the number of variables in the 3SAT proposition, and succeeds with high probability to correctly decide 3SAT.^{[5]}
The exponential time hypothesis asserts that no algorithm can solve 3SAT (or indeed kSAT for any k > 2) in time that is fundamentally faster than exp(o(n)).
Selman, Mitchell, and Levesque (1996) give empirical data on the difficulty of randomly generated 3SAT formulas, depending on their size parameters. Difficulty is measured in number recursive calls made by a DPLL algorithm.^{[6]}
3satisfiability can be generalized to ksatisfiability (kSAT, also kCNFSAT), 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 3SAT nor harder than SAT, and the latter two are NPcomplete, so must be kSAT.
Some authors restrict kSAT to CNF formulas with exactly k literals. This doesn't lead to a different complexity class either, as each clause "l_{1} ∨ ... ∨ l_{j}" with j<k literals can be padded with fixed dummy variables to "l_{1} ∨ ... ∨ l_{j} ∨ d_{j+1} ∨ ... ∨ d_{k}". After padding all clauses, 2^{k}1 extra clauses^{[note 4]} have to be appended to ensure that only d_{1}=...=d_{k}=FALSE can lead to a satisfying assignment. Since k doesn't depend on the formula length, the extra clauses lead to a constant increase in length. For the same reason, it does not matter whether duplicate literals are allowed in clauses (like e.g. "¬x ∨ ¬y ∨ ¬y"), or not.
Exactly1 3satisfiability
Left: Schaefer's reduction of a 3SAT clause x∨y∨z. The result of R is TRUE (1) if exactly one of its arguments is TRUE, and FALSE (0) otherwise. All 8 combinations of values for x,y,z are examined, one per line. The fresh variables a,...,f can be chosen to satisfy all clauses (exactly one green argument for each R) in all lines except the first, where x∨y∨z is FALSE. Right: A simpler reduction with the same properties.
A variant of the 3satisfiability problem is the oneinthree 3SAT (also known variously as 1in3SAT and exactly1 3SAT). Given a conjunctive normal form, the 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. Formally, a oneinthree 3SAT problem is given as a generalized conjunctive normal form with all generalized clauses using a ternary operator R that is TRUE just if exactly one of its arguments is. When all literals of a oneinthree 3SAT formula are positive, the satisfiability problem is called oneinthree positive 3SAT.
Oneinthree 3SAT, together with its positive case, is listed as NPcomplete problem "LO4" in the standard reference, Computers and Intractability: A Guide to the Theory of NPCompleteness by Michael R. Garey and David S. Johnson. Oneinthree 3SAT was proved to be NPcomplete 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 NPcomplete.^{[7]}
Schaefer gives a construction allowing an easy polynomialtime reduction from 3SAT to oneinthree 3SAT. Let "(x or y or z)" be a clause in a 3CNF formula. Add six fresh boolean variables a, b, c, d, e, and f, to be used to simulate this clause and no other. Then the formula R(x,a,d) ∧ R(y,b,d) ∧ R(a,b,e) ∧ R(c,d,f) ∧ R(z,c,FALSE) is satisfiable by some setting of the fresh variables if and only if at least one of x, y, or z is TRUE, see picture (left). Thus any 3SAT instance with m clauses and n variables may be converted into an equisatisfiable oneinthree 3SAT instance with 5m clauses and n+6m variables.^{[8]} Another reduction involves only four fresh variables and three clauses: R(¬x,a,b) ∧ R(b,y,c) ∧ R(c,d,¬z), see picture (right).
2satisfiability
SAT is easier if the number of literals in a clause is limited to at most 2, in which case the problem is called 2SAT. This problem can be solved in polynomial time, and in fact is complete for the complexity class NL. If additionally all OR operations in literals are changed to XOR operations, the result is called exclusiveor 2satisfiability, which is a problem complete for the complexity class SL = L.
Hornsatisfiability
The problem of deciding the satisfiability of a given conjunction of Horn clauses is called Hornsatisfiability, or HORNSAT. It can be solved in polynomial time by a single step of the Unit propagation algorithm, which produces the single minimal model of the set of Horn clauses (w.r.t. the set of literals assigned to TRUE). Hornsatisfiability is Pcomplete. It can be seen as P's version of the Boolean satisfiability problem.
Horn clauses are of interest because they are able to express implication of one variable from a set of other variables. Indeed, one such clause ¬x_{1} ∨ ... ∨ ¬x_{n} ∨ y can be rewritten as x_{1} ∧ ... ∧ x_{n} → y, that is, if x_{1},...,x_{n} are all TRUE, then y needs to be TRUE as well.
A generalization of the class of Horn formulae is that of renamableHorn formulae, which is the set of formulae that can be placed in Horn form by replacing some variables with their respective negation. For example, (x_{1} ∨ ¬x_{2}) ∧ (¬x_{1} ∨ x_{2} ∨ x_{3}) ∧ ¬x_{1} is not a Horn formula, but can be renamed to the Horn formula (x_{1} ∨ ¬x_{2}) ∧ (¬x_{1} ∨ x_{2} ∨ ¬y_{3}) ∧ ¬x_{1} by introducing y_{3} as negation of x_{3}. In contrast, no renaming of (x_{1} ∨ ¬x_{2} ∨ ¬x_{3}) ∧ (¬x_{1} ∨ x_{2} ∨ x_{3}) ∧ ¬x_{1} leads to a Horn formula. Checking the existence of such a replacement can be done in linear time; therefore, the satisfiability of such formulae is in P as it can be solved by first performing this replacement and then checking the satisfiability of the resulting Horn formula.
A formula with 2 clauses may be unsatisfied (red), 3satisfied (green), xor3satisfied (blue), or/and 1in3satisfied (yellow), depending on the TRUEliteral count in the 1st (hor) and 2nd (vert) clause.

XORsatisfiability
Solving an XORSAT example
by Gaussian elimination

Given formula

("⊕" means XOR, the red clause is optional)

(a⊕c⊕d) ∧ (b⊕¬c⊕d) ∧ (a⊕b⊕¬d) ∧ (a⊕¬b⊕¬c) ∧ (¬a⊕b⊕c)


Equation system

("1" means TRUE, "0" means FALSE)

Each clause leads to one equation.


a

⊕


c

⊕


d

= 1


b

⊕

¬

c

⊕


d

= 1


a

⊕


b

⊕

¬

d

= 1


a

⊕

¬

b

⊕

¬

c

= 1

¬

a

⊕


b

⊕


c

≃ 1


Normalized equation system

using properties of Boolean rings (¬x=1⊕x, x⊕x=0)

a

⊕

c

⊕

d

= 1

b

⊕

c

⊕

d

= 0

a

⊕

b

⊕

d

= 0

a

⊕

b

⊕

c

= 1

a

⊕

b

⊕

c

≃ 0

(If the red equation is present, it contradicts

the last black one, so the system is unsolvable.

Therefore, Gauss' algorithm is

used only for the black equations.)


Associated coefficient matrix


a

b

c

d


line


1

0

1

1

1

A

0

1

1

1

0

B

1

1

0

1

0

C

1

1

1

0

1

D


Transforming to echelon form


a

b

c

d


operation


1

0

1

1

1

A

1

1

0

1

0

C

1

1

1

0

1

D

0

1

1

1

0

B (swapped)


1

0

1

1

1

A

0

1

1

0

1

E = C⊕A

0

1

0

1

0

F = D⊕A

0

1

1

1

0

B


1

0

1

1

1

A

0

1

1

0

1

E

0

0

1

1

1

G = F⊕E

0

0

0

1

1

H = B⊕E


Transforming to diagonal form


a

b

c

d


operation


1

0

1

0

0

I = A⊕H

0

1

1

0

1

E

0

0

1

0

0

J = G⊕H

0

0

0

1

1

H


1

0

0

0

0

K = I⊕J

0

1

0

0

1

L = E⊕J

0

0

1

0

0

J

0

0

0

1

1

H


Solution:

If the red clause is present:

Unsolvable

Else:

a = 0 = FALSE


b = 1 = TRUE


c = 0 = FALSE


d = 1 = TRUE

As a consequence:

R(a,c,d) ∧ R(b,¬c,d) ∧ R(a,b,¬d) ∧ R(a,¬b,¬c) ∧ R(¬a,b,c)

is not 1in3satisfiable,

while (a∨c∨d) ∧ (b∨¬c∨d) ∧ (a∨b∨¬d) ∧ (a∨¬b∨¬c)

is 3satisfiable with a=c=FALSE and b=d=TRUE.


Another special case is the class of problems where each clause contains XOR (i.e. exclusive or) rather than (plain) OR operators.^{[note 5]} This is in P, since an XORSAT formula can also be viewed as a system of linear equations mod 2, and can be solved in cubic time by Gaussian elimination;^{[9]} see the box for an example. This recast is based on the kinship between Boolean algebras and Boolean rings, and the fact that arithmetic modulo two forms a finite field. Since a XOR b XOR c evaluates to TRUE if and only if exactly 1 or 3 members of {a,b,c} are TRUE, each solution of the 1in3SAT problem for a given CNF formula is also a solution of the XOR3SAT problem, and in turn each solution of XOR3SAT is a solution of 3SAT, cf. picture. As a consequence, for each CNF formula, it is possible to solve the XOR3SAT problem defined by the formula, and based on the result infer either that the 3SAT problem is solvable or that the 1in3SAT problem is unsolvable.
Provided that the complexity classes P and NP are not equal, neither 2, nor Horn, nor XORsatisfiability is NPcomplete, unlike SAT. The assumption that P and NP are not equal is currently not proven.
Schaefer's dichotomy theorem
The restrictions above (CNF, 2CNF, 3CNF, Horn, XORSAT) bound the considered formulae to be conjunctions of subformulae; each restriction states a specific form for all subformulae: for example, only binary clauses can be subformulae in 2CNF.
Schaefer's dichotomy theorem states that, for any restriction to Boolean operators that can be used to form these subformulae, the corresponding satisfiability problem is in P or NPcomplete. The membership in P of the satisfiability of 2CNF, Horn, and XORSAT formulae are special cases of this theorem.
Extensions of SAT
An extension that has gained significant popularity since 2003 is Satisfiability modulo theories (SMT) that can enrich CNF formulas with linear constraints, arrays, alldifferent constraints, uninterpreted functions,^{[10]} etc. Such extensions typically remain NPcomplete, but very efficient solvers are now available that can handle many such kinds of constraints.
The satisfiability problem becomes more difficult if both "for all" (∀) and "there exists" (∃) quantifiers are allowed to bind the Boolean variables. An example of such an expression would be "∀x ∀y ∃z (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)"; it is valid, since for all values of x and y, an appropriate value of z can be found, viz. z=TRUE if both x and y are FALSE, and z=FALSE else. SAT itself (tacitly) uses only ∃ quantifiers. If only ∀ quantifiers are allowed instead, the socalled tautology problem is obtained, which is coNPcomplete. If both quantifiers are allowed, the problem is called the quantified Boolean formula problem (QBF), which can be shown to be PSPACEcomplete. It is widely believed that PSPACEcomplete problems are strictly harder than any problem in NP, although this has not yet been proved.
A number of variants deal with the number of variable assignments making the formula TRUE. Ordinary SAT asks if there is at least one such assignment. MAJSAT, which asks if the majority of all assignments make the formula TRUE, is complete for PP, a probabilistic class. The problem of how many variable assignments satisfy a formula, not a decision problem, is in #P. UNIQUESAT is the problem of determining whether a formula has exactly one assignment; it is complete for US, the complexity class describing problems solvable by a nondeterministic polynomial time Turing machine that accepts when there is exactly one nondeterministic accepting path and rejects otherwise. When the input is restricted to formulas having at most one satisfying assignment (or none), the problem is called UNAMBIGUOUSSAT. A solving algorithm for UNAMBIGUOUSSAT is allowed to exhibit any behavior, including endless looping, on a formula having several satisfying assignments. Although this problem seems easier, Valiant and Vazirani have shown^{[11]} that if there is a practical (i.e. randomized polynomialtime) algorithm to solve it, then all problems in NP can be solved just as easily.
The maximum satisfiability problem, an FNP generalization of SAT, asks for the maximum number of clauses which can be satisfied by any assignment. It has efficient approximation algorithms, but is NPhard to solve exactly. Worse still, it is APXcomplete, meaning there is no polynomialtime approximation scheme (PTAS) for this problem unless P=NP.
Other generalisations include satisfiability for first and secondorder logic, constraint satisfaction problems, 01 integer programming.
Selfreducibility
The SAT problem is selfreducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment. First, the question is asked on the given formula Φ. If the answer is "no", the formula is unsatisfiable. Otherwise, the question is asked on the partly instantiated formula Φ{x_{1}=TRUE}, i.e. Φ with the first variable x_{1} replaced by TRUE, and simplified accordingly. If the answer is "yes", then x_{1}=TRUE, otherwise x_{1}=FALSE. Values of other variables can be found subsequently in the same way. In total, n+1 runs of the algorithm are required, where n is the number of distinct variables in Φ.
This property of selfreducibility is used in several theorems in complexity theory:

NP ⊆ P/poly ⇒ PH = Σ_{2} (Karp–Lipton theorem)

NP ⊆ BPP ⇒ NP = RP

P = NP ⇒ FP = FNP
Algorithms for solving SAT
Since the SAT problem is NPcomplete, only algorithms with exponential worstcase complexity are known for it. In spite of this state of the art in complexity theory, efficient and scalable algorithms for SAT were developed over the last decade and have contributed to dramatic advances in our ability to automatically solve problem instances involving tens of thousands of variables and millions of constraints (i.e. clauses).^{[12]} Examples of such problems in electronic design automation (EDA) include formal equivalence checking, model checking, formal verification of pipelined microprocessors,^{[10]} automatic test pattern generation, routing of FPGAs,^{[13]} planning, and scheduling problems, and so on. A SATsolving engine is now considered to be an essential component in the EDA toolbox.
There are two classes of highperformance algorithms for solving instances of SAT in practice: the ConflictDriven Clause Learning algorithm, which can be viewed as a modern variant of the DPLL algorithm (well known implementations include Chaff^{[14]} and GRASP^{[15]}) and stochastic local search algorithms, such as WalkSAT.
A DPLL SAT solver employs a systematic backtracking search procedure to explore the (exponentially sized) space of variable assignments looking for satisfying assignments. The basic search procedure was proposed in two seminal papers in the early 1960s (see references below) and is now commonly referred to as the Davis–Putnam–Logemann–Loveland algorithm ("DPLL" or "DLL").^{[16]}^{[17]} Theoretically, exponential lower bounds have been proved for the DPLL family of algorithms.
In contrast, randomized algorithms like the PPSZ algorithm by Paturi, Pudlak, Saks, and Zane set variables in a random order according to some heuristics, for example boundedwidth resolution. If the heuristic can't find the correct setting, the variable is assigned randomly. The PPSZ algorithm has a runtime of O(2^{0.386n}) for 3SAT with a single satisfying assignment. Currently this is the best known runtime for this problem. In the setting with many satisfying assignments the randomized algorithm by Schöning has a better bound.^{[5]}^{[18]}
Modern SAT solvers (developed in the last ten years) come in two flavors: "conflictdriven" and "lookahead". Conflictdriven solvers augment the basic DPLL search algorithm with efficient conflict analysis, clause learning, nonchronological backtracking (a.k.a. backjumping), as well as "twowatchedliterals" unit propagation, adaptive branching, and random restarts. These "extras" to the basic systematic search have been empirically shown to be essential for handling the large SAT instances that arise in electronic design automation (EDA).^{[19]} Lookahead solvers have especially strengthened reductions (going beyond unitclause propagation) and the heuristics, and they are generally stronger than conflictdriven solvers on hard instances (while conflictdriven solvers can be much better on large instances which actually have an easy instance inside).
Modern SAT solvers are also having significant impact on the fields of software verification, constraint solving in artificial intelligence, and operations research, among others. Powerful solvers are readily available as free and open source software. In particular, the conflictdriven MiniSAT, which was relatively successful at the 2005 SAT competition, only has about 600 lines of code. A modern Parallel SAT solver is ManySAT. It can achieve super linear speedups on important classes of problems. An example for lookahead solvers is march_dl, which won a prize at the 2007 SAT competition.
Certain types of large random satisfiable instances of SAT can be solved by survey propagation (SP). Particularly in hardware design and verification applications, satisfiability and other logical properties of a given propositional formula are sometimes decided based on a representation of the formula as a binary decision diagram (BDD).
Almost all SAT solvers include timeouts, so they will terminate in reasonable time even if they cannot find a solution. Different SAT solvers will find different instances easy or hard, and some excel at proving unsatisfiability, and others at finding solutions. All of these behaviors can be seen in the SAT solving contests.^{[20]}
See also
Notes

^ The SAT problem for arbitrary formulas is NPcomplete, too, since it is easily shown to be in NP, and it cannot be easier than SAT for CNF formulas.

^ i.e. at least as hard as every other problem in NP. A decision problem is NPcomplete if and only if it is in NP and is NPhard.

^ i.e. such that one literal isn't the negation of the other

^ viz. all maxterms that can be built with d_{1},...,d_{k}, except "d_{1}∨...∨d_{k}"

^ Formally, generalized conjunctive normal forms with a ternary boolean operator R are employed, which is TRUE just if 1 or 3 of its arguments is. An input clause with more than 3 literals can be transformed into an equisatisfiable conjunction of clauses á 3 literals similar to above; i.e. XORSAT can be reduced to XOR3SAT.
References

^

^ (pdf) (Russian), translated into English by

^ ^{a} ^{b} ; here: Thm.10.4

^ Aho, Hopcroft, Ullman^{[3]} (1974); Thm.10.5

^ ^{a} ^{b}

^

^

^ (Schaefer, 1978), p.222, Lemma 3.5

^ .

^ ^{a} ^{b} R. E. Bryant, S. M. German, and M. N. Velev, Microprocessor Verification Using Efficient Decision Procedures for a Logic of Equality with Uninterpreted Functions, in Analytic Tableaux and Related Methods, pp. 1–13, 1999.

^

^ .

^

^

^

^

^

^ "An improved exponentialtime algorithm for kSAT", Paturi, Pudlak, Saks, Zani

^

^
References are ordered by date of publication:

A9.1: LO1 – LO7, pp. 259 – 260.







External links
SAT problem format
A SAT problem is often described in the DIMACSCNF format: an input file in which each line represents a single disjunction. For example, a file with the two lines
1 5 4 0
1 5 3 4 0
represents the formula "(x_{1} ∨ ¬x_{5} ∨ x_{4}) ∧ (¬x_{1} ∨ x_{5} ∨ x_{3} ∨ x_{4})".
Another common format for this formula is the 7bit ASCII representation "(x1  ~x5  x4) & (~x1  x5  x3  x4)".

BCSAT is a tool that converts input files in humanreadable format to the DIMACSCNF format.
Online SAT solvers

BoolSAT – Solves formulas in the DIMACSCNF format or in a more humanfriendly format: "a and not b or a". Runs on a server.

Logictools  Provides different solvers in javascript for learning, comparison and hacking. Runs in the browser.

minisatinyourbrowser – Solves formulas in the DIMACSCNF format. Runs in the browser.

SATRennesPA  Solves formulas written in a userfriendly way. Runs on a server.

somerby.net/mack/logic  Solves formulas written in symbolic logic. Runs in the browser.
Offline SAT solvers

MiniSAT – DIMACSCNF format.

Lingeling – won a gold medal in a 2011 SAT competition.

PicoSAT – an earlier solver from the Lingeling group.

Sat4j – DIMACSCNF format. Java source code available.

Glucose – DIMACSCNF format.

RSat – won a gold medal in a 2007 SAT competition.

UBCSAT. Supports unweighted and weighted clauses, both in the DIMACSCNF format. C source code hosted on GitHub.

CryptoMiniSat – won a gold medal in a 2011 SAT competition. C++ source code hosted on GitHub. Tries to put many useful features of MiniSat 2.0 core, PrecoSat ver 236, and Glucose into one package, adding many new features

Spear – Supports bitvector arithmetic. Can use the DIMACSCNF format or the Spear format.

HyperSAT – Written to experiment with Bcubing search space pruning. Won 3rd place in a 2005 SAT competition. An earlier and slower solver from the developers of Spear.

BASolver

ArgoSAT

Fast SAT Solver – based on genetic algorithms.

zChaff – not supported anymore.

BCSAT – humanreadable boolean circuit format (also converts this format to the DIMACSCNF format and automatically links to MiniSAT or zChaff).
SAT applications

WinSAT v2.04: A Windowsbased SAT application made particularly for researchers.
Conferences
International Conference on Theory and Applications of Satisfiability Testing:

SAT 2013

SAT 2012

SAT 2011

SAT 2010

SAT 2009

SAT 2008

SAT 2007
Publications

Journal on Satisfiability, Boolean Modeling and Computation

Survey Propagation
Benchmarks

Forced Satisfiable SAT Benchmarks

SATLIB

Software Verification Benchmarks

Fadi Aloul SAT Benchmarks
SAT solving in general:

http://www.satlive.org

http://www.satisfiability.org
Evaluation of SAT solvers

Yearly evaluation of SAT solvers

SAT solvers evaluation results for 2008

International SAT Competitions

History
More information on SAT:

SAT and MAXSAT for the Layresearcher
This article includes material from a column in the ACM SIGDA enewsletter by Prof. Karem Sakallah
Original text is available here
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.