3-SAT

3-SAT is the problem of determining whether a given Boolean formula in conjunctive normal form, where each clause contains exactly three literals, is satisfiable. It is a restricted special case of Boolean satisfiability (SAT) that remains NP-complete, and it is the canonical problem used in complexity theory to establish NP-completeness via reduction.

The significance of 3-SAT extends beyond its theoretical status. Random instances of 3-SAT exhibit a sharp satisfiability phase transition: as the ratio of clauses to variables increases, the probability of satisfiability drops abruptly from near-certain to near-impossible. This transition, located at approximately α ≈ 4.267, has been studied extensively using methods from statistical physics, including the cavity method and replica symmetry breaking. The hardest instances for both complete and incomplete solvers are found near this threshold, making 3-SAT a natural testbed for understanding computational hardness in practice.