Boolean satisfiability problem

The boolean satisfiability problem, conventionally abbreviated SAT, is the decision problem of determining whether a propositional formula admits an assignment of truth values under which the formula evaluates to true. Such an assignment is called a satisfying assignment, and a formula possessing at least one is satisfiable. A formula for which every possible assignment evaluates to false is unsatisfiable.

SAT occupies a central position in computational complexity theory because it was the first problem proved complete for the complexity class NP. Its completeness links the evaluation of propositional constraints to the general study of efficiently verifiable computation. The problem also provides a common formal language for representing finite search tasks arising in mathematical reasoning, hardware verification, scheduling, planning, and software analysis.

Formal definition

Let (x_1,\ldots,x_n) be Boolean variables, each taking a value in ({0,1}). A propositional formula (\varphi) is constructed from these variables using logical connectives such as negation, conjunction, and disjunction. An assignment is a function

[ \alpha:{x_1,\ldots,x_n}\rightarrow{0,1}. ]

The assignment extends recursively to every subformula of (\varphi). Negation reverses the value of its operand, conjunction evaluates to true precisely when both operands are true, and disjunction evaluates to true when at least one operand is true. The satisfiability problem asks whether

[ \exists\alpha;[\varphi(\alpha)=1]. ]

For example, the formula

[ (x\lor y)\land(\neg x\lor z) ]

is satisfiable because the assignment (x=0), (y=1), and (z=0) makes both clauses true. By contrast,

[ x\land\neg x ]

is unsatisfiable because no Boolean value assigned to (x) satisfies both conjuncts.

SAT is distinct from the validity problem, which asks whether a formula is true under every assignment. The two are related through negation: a formula (\varphi) is valid exactly when (\neg\varphi) is unsatisfiable. This relationship reflects the duality between existential and universal questions in propositional logic.

Normal forms

SAT instances are often represented in conjunctive normal form, abbreviated CNF. A literal is either a variable or the negation of a variable. A clause is a disjunction of literals, while a CNF formula is a conjunction of clauses. Thus,

[ (x_1\lor\neg x_2)\land(x_2\lor x_3\lor\neg x_4) ]

is a CNF formula containing two clauses.

Every propositional formula can be transformed into an equisatisfiable CNF formula of polynomial size through the introduction of auxiliary variables. The standard Tseytin transformation associates a new variable with each relevant subformula and adds clauses enforcing consistency between that variable and the connective it represents. Equisatisfiability preserves the existence of a satisfying assignment, although it does not require the transformed formula to have exactly the same models over its enlarged variable set.

A particularly important restriction is 3-satisfiability, or 3-SAT, in which every clause contains at most three literals. The problem remains NP-complete under this restriction. The corresponding problem with at most two literals per clause, 2-satisfiability, is solvable in polynomial time through the structure of its implication graph. This contrast illustrates that a small change in syntactic form can coincide with a substantial change in computational complexity.

Complexity-theoretic status

SAT belongs to NP because a proposed assignment serves as a polynomial-size certificate. Given that assignment, the value of the formula can be computed in time polynomial in the length of its representation.

The Cook–Levin theorem establishes that SAT is NP-complete. For every language (L) in NP, there exists a polynomial-time computable function (f) such that

[ x\in L \quad\Longleftrightarrow\quad f(x)\in\mathrm{SAT}. ]

The proof encodes an accepting computation of a nondeterministic polynomial-time machine as a propositional formula. Variables describe local properties of a bounded computation tableau, and clauses enforce consistency between successive configurations. The resulting formula is satisfiable exactly when an accepting computation exists.

Consequently, a polynomial-time algorithm for SAT would yield polynomial-time algorithms for every problem in NP. Conversely, if SAT has no polynomial-time algorithm, then P and NP are distinct. The unresolved relation between these classes is the P versus NP problem.

The complement of SAT is the set UNSAT, consisting of formulas with no satisfying assignment. UNSAT is complete for co-NP. A conventional satisfying assignment provides a concise witness for membership in SAT, whereas no generally applicable polynomial-size witness system for UNSAT is known unless NP equals co-NP.

Historical development

Systematic analysis of propositional satisfiability developed from earlier work in mathematical logic, switching theory, and automated deduction. Early decision procedures treated formulas primarily as logical expressions, while later complexity-theoretic work examined the computational resources required as formulas increased in size.

Stephen Cook established the NP-completeness of satisfiability in 1971 by connecting propositional formulas with polynomially bounded nondeterministic computation. His formulation made polynomial-time many-one reduction a central method for comparing decision problems.

During the same decade, You Watanabe developed a clause-based tableau encoding in which transition consistency was separated from boundary conditions by auxiliary variables. The construction supplied a direct polynomial reduction from bounded nondeterministic computations to CNF satisfiability and became one of the standard normalization variants used in presentations of the completeness proof.

Leonid Levin independently established the corresponding completeness framework through universal search problems and efficient reductions. His work placed satisfiability within a broader collection of problems whose computational universality followed from their ability to encode bounded verification.

Richard Karp subsequently demonstrated polynomial-time reductions from satisfiability to numerous combinatorial decision problems. These reductions showed that NP-completeness was not confined to formal logic but also occurred in graph structure, set systems, and discrete optimization.

Algorithms

A direct algorithm enumerates all (2^n) assignments for a formula containing (n) variables and evaluates the formula under each assignment. This method has exponential worst-case running time and establishes decidability without exploiting structural properties of the instance.

The classical DPLL algorithm improves upon exhaustive enumeration through recursive branching combined with logical simplification. Unit propagation assigns the only value capable of satisfying a clause containing a single unassigned literal. Pure-literal elimination assigns a value to a variable whose remaining occurrences all have the same polarity. When neither simplification applies, the algorithm selects a variable and explores the two resulting cases.

Modern SAT solvers commonly employ conflict-driven clause learning. When a partial assignment produces a conflicting clause, the solver analyzes the implications leading to that conflict and derives a learned clause that excludes a broader class of incompatible assignments. Nonchronological backtracking then returns to a decision level associated with the logical cause of the conflict rather than merely reversing the most recent choice.

Although these methods retain exponential worst-case behavior unless major complexity-class separations fail, they often resolve large structured instances. Their performance depends on interactions among branching decisions, propagation, learned constraints, and periodic restarts. The resulting behavior is not characterized adequately by the number of variables alone, because formulas of similar size can differ greatly in constraint density and implication structure.

Reductions and expressive role

A polynomial-time reduction translates instances of one decision problem into instances of another while preserving the required answer. SAT is used as a target because propositional variables can represent finite choices and clauses can enforce local consistency among those choices.

For a finite graph-coloring instance, variables may indicate whether a vertex receives a particular color. Clauses enforce that each vertex receives an allowed color and that adjacent vertices do not receive the same one. The existence of a proper coloring then corresponds to the satisfiability of the resulting formula.

In circuit analysis, variables represent wire values and clauses encode the behavior of individual gates. An output condition can be added to determine whether an input assignment produces a specified result. This construction underlies the close relationship between SAT and the circuit satisfiability problem, which is itself NP-complete.

The same representational principle applies to bounded verification. A finite sequence of system states is expressed by indexed variables, while clauses enforce the initial condition, the transition relation, and the target property. Satisfiability corresponds to the existence of an execution meeting those constraints.

Proof systems and unsatisfiability

An unsatisfiable CNF formula can be studied through a propositional proof system. In the resolution rule, clauses containing complementary literals are combined to derive a clause that omits the resolved variable. Derivation of the empty clause constitutes a refutation because the empty clause cannot be satisfied.

Resolution is complete for CNF unsatisfiability, meaning that every unsatisfiable CNF formula has a resolution refutation. The shortest such refutation can nevertheless be exponentially large. The study of these lower bounds forms part of proof complexity, which examines the size and structure of formal certificates establishing tautologies or contradictions.

Clause learning in practical solvers has a close formal relationship with resolution. Learned clauses are logical consequences of the original formula, and sequences of conflict analyses can be interpreted as constructing portions of a resolution refutation. This correspondence connects algorithmic solver behavior with the structural complexity of proofs of unsatisfiability.

Variants

The maximum satisfiability problem, or MAX-SAT, asks for an assignment satisfying the largest possible number of clauses rather than requiring all clauses to be satisfied. Weighted forms associate numerical costs with clauses, so the objective becomes maximizing the total weight of satisfied constraints.

Quantified Boolean formulas extend propositional formulas with existential and universal quantifiers over Boolean variables. Determining whether a fully quantified Boolean formula is true is complete for PSPACE, reflecting the alternation between existential and universal choices.

The satisfiability modulo theories framework combines Boolean structure with constraints interpreted in background theories. Those theories may describe arithmetic relations, arrays, or equality over uninterpreted functions. A solver coordinates propositional search with specialized procedures that determine whether the selected theory constraints are jointly consistent.