Universal Crossover Scaling of the P–NP Transition: Experimental Evidence from 2-SAT to k-SAT Interpolation

The P versus NP problem is a central open question in theoretical computer science and one of the seven Millennium Prize Problems. This work presents a comprehensive experimental investigation of the continuous transition from polynomial 2‑SAT to NP‑complete 3‑SAT by systematically tuning the fraction *p* of 3‑SAT clauses. The central discovery is a universal crossover scaling law for the critical fraction pc(n) at which the solution space fragments (Overlap Gap Property): pc(n) = A · *n*‑δeff(n), δeff(n) = δ∞ + (δ0 – δ∞) e‑n/nc, with fitted parameters A = 0.704 ± 0.015, δ∞ = 0.576 ± 0.009, δ0 = 1.048 ± 0.027, and crossover scale nc = 5.51 ± 0.18 (R² = 0.967 on 18 independent points from *n* = 3 to 19). This law demonstrates that in the thermodynamic limit (*n* → ∞), an arbitrarily small admixture of 3‑SAT clauses suffices to break ergodicity and induce computational hardness. Universality is further confirmed by a preliminary measurement for the 3‑SAT → 4‑SAT transition at *n* = 12 (pc = 0.063 ± 0.021, consistently lower than the 2 → 3 value of 0.086 ± 0.047). Complementary experiments—including direct detection of persistent second Betti numbers (438 persistent β₂ intervals at *n* = 100), Overlap Gap Ratio quantification (OGR = 4.62 ± 1.46 on SATLIB benchmarks), replica exchange Monte Carlo, and macroscopic geometric scaling laws—all converge to the same conclusion: NP‑completeness is characterized by a topological fragmentation of the solution space governed by a scale‑invariant power law. The findings provide a robust quantitative empirical foundation for the conjecture P ≠ NP and offer a precise benchmark for future rigorous theories of computational phase transitions.