boolean satisfiability

Boolean satisfiability, SAT, is a yes/no puzzle about logic switches. You are given a formula built from true/false variables joined by AND, OR, and NOT, and you must answer one question: is there ANY way to set the switches, each to true or false, that makes the whole formula come out true? It is the question 'can these constraints all be met at once?' stripped down to pure logic.

Most often SAT is stated in conjunctive normal form (CNF): the formula is an AND of clauses, and each clause is an OR of literals, where a literal is a variable or its negation. A clause like (x1 OR NOT x2 OR x3) demands that at least one of its literals be true; the AND demands every clause be satisfied at once. SAT asks whether some assignment of true/false to x1, x2, x3, ... satisfies all clauses simultaneously. For example (x1 OR x2) AND (NOT x1 OR NOT x2) is satisfiable: set x1 true and x2 false. By contrast x1 AND (NOT x1) is unsatisfiable, no setting works.

SAT is the first problem proven NP-complete, by the Cook-Levin theorem, which makes it the historical and conceptual centre of the theory. Verifying a 'yes' is trivial (plug in the assignment and evaluate, a clean polynomial-time verifier), so SAT is in NP; Cook-Levin shows it is also NP-hard. In practice SAT is everywhere: hardware and software verification, planning, scheduling, and cryptanalysis all reduce to it. Despite its NP-completeness, industrial SAT solvers routinely crack formulas with millions of variables, a striking reminder that worst-case hardness does not mean every instance is hard.