Algorithms, data structures and procedures for determining whether a propositional Boolean formula (typically in CNF) is satisfiable, and for producing a satisfying assignment when one exists; modern SAT solving includes DPLL, CDCL, heuristics, clause learning, restarts and preprocessing.

Principle

Systematically search for a Boolean assignment that satisfies all clauses using backtracking search (DPLL style), augmented by conflict-driven clause learning (CDCL), unit propagation, variable selection heuristics, and proof recording or unsat core extraction to improve efficiency and provide evidence of unsatisfiability.

Demonstration

Given a CNF instance encoding a scheduling constraint, a CDCL SAT solver performs unit propagation to deduce forced assignments, branches on a chosen variable, records learned clauses from conflicts to avoid repeating bad partial assignments, and eventually returns a full assignment satisfying every clause or a proof of unsatisfiability.

Misapplication

Feeding a SAT solver a problem without an appropriate encoding (losing semantics), expecting worst-case polynomial behaviour on NP-complete instances, or misreading a solver's 'unknown' or time‑out result as satisfiable or unsatisfiable without further analysis.

Consequence

SAT solvers provide highly effective engines for many practical NP problems via encodings (planning, verification, synthesis), produce concrete models for satisfiable instances, and can give resolution proofs or unsat cores for unsatisfiable cases; they scale well in practice despite worst‑case hardness.

Reversal

Counting solutions (#SAT) or solving quantified Boolean formulas (QBF) inverts SAT solving by addressing enumeration or additional quantifier alternations, both of which are strictly harder and require different algorithms and complexity considerations.

Boundary

Applies to propositional logic; problems must be encoded (often to CNF) and solver effectiveness depends heavily on encoding quality and heuristics. SAT solving is decidable and complete for propositional logic but does not directly handle theories (use SMT for theory reasoning).

Semantic Tension

There is tension between SAT and constraint programming or SMT: SAT relies on Boolean encodings and clause learning, while CP uses richer domains and propagation; SMT relaxes SAT by embedding theories, trading raw Boolean performance for expressiveness.

Synthesis

SAT solving is a mature, highly engineering‑driven approach to deciding propositional satisfiability: it combines systematic search with powerful inference and learning mechanisms to produce assignments or proofs, and serves as a backend for many higher‑level reasoning tasks via encoding.