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

This work does not claim a formal proof of P ≠ NP. Instead, it provides a comprehensive experimental characterization of the continuous transition from 2-SAT (in P) to 3-SAT (NP-complete) by systematically tuning the fraction of 3-SAT clauses. The central discovery is a universal crossover scaling law for the critical fraction p_c(n) at which the solution space fragments (Overlap Gap Property): p_c(n) = A · n-δ_eff(n), with fitted parameters A = 2.70 ± 0.15, δ_∞ = 1.38 ± 0.05, δ_0 = 2.94 ± 0.10, n_c = 2.77 ± 0.20 (R²_log = 0.956 on 18 independent points from n = 3 to 19). Universality is confirmed for the 3-SAT → 4-SAT transition (p_c = 0.063 ± 0.021 at n = 12). Complementary experiments include direct detection of persistent second Betti numbers (β_2 = 438 persistent two-dimensional holes at n = 100), Overlap Gap Ratio quantification (OGR = 4.62 ± 1.46 on SATLIB benchmarks), replica exchange Monte Carlo, and extensive algorithmic comparisons. All evidence converges to the conclusion that NP-completeness is characterized by a topological fragmentation of the solution space, governed by a universal, scale-invariant power law. A geometric taxonomy of NP-complete problems is constructed, demonstrating that only the k-SAT family exhibits strong Replica Symmetry Breaking (OGR > 1.5, MP > 5%, β_2 > 0), while graph-based problems (MAX-CUT, Vertex Cover, 3-COL) show weak fragmentation and numerical problems (Subset Sum) show none. These findings provide a robust quantitative empirical foundation for the conjecture P ≠ NP and reframe the problem as an observable physical phase transition in the space of computation. This record includes the complete dataset supporting the study (crossover data, taxonomy metrics, algorithm scaling) and the final preprint PDF.