UNSAT

UNSAT, short for unsatisfiable, refers to a property of propositional formulas in logic and computer science. A formula is unsatisfiable if there is no assignment of truth values to its variables that makes the formula true. In the context of SAT problems, UNSAT denotes the complement of the satisfiable (SAT) problem: a given formula is unsatisfiable if it has no satisfying assignment.

The decision problem UNSAT is studied in the area of computational complexity. When formulas are presented in conjunctive normal form (CNF), determining unsatisfiability is a co-NP-complete problem. This means that, unless NP equals co-NP, there is no known polynomial-time algorithm that, for every CNF formula, certifies unsatisfiability. In contrast, the satisfiability problem (SAT) is NP-complete. Some restricted subclasses behave differently; for example, 2-CNF formulas can be decided as unsatisfiable in polynomial time, while general k-CNF with k ≥ 3 remains co-NP-complete for UNSAT.

In practice, unsatisfiability can be certified by proofs. A common form is a resolution refutation, which provides a certificate that can be checked in polynomial time given the proof. Modern SAT solvers can return UNSAT results for formulas and often generate certificates or proofs to verify unsatisfiability independently.

UNSAT is central to theoretical and applied areas such as automated theorem proving, formal verification, and constraint solving. It contrasts with SAT and with tautology problems, and, together with their certificates, underpins formal guarantees about the (in)feasibility of logical constraints.