Boolean satisfiability threshold: at α_c ≈ 4.267, problems transition from easy-SAT to hard-UNSAT
3-SAT: M clauses of 3 literals over N boolean vars — is there a satisfying assignment?
Threshold: α_c ≈ 4.267 (Mézard, Parisi, Zecchina 2002 — cavity method / belief propagation)
Hardness peak: algorithmic complexity spikes near α_c — polynomial far from threshold
Connection: spin glass phase transition — replica symmetry breaking below α_c (Parisi 2006)