Experimental Discovery of a Universal Continuous Topological Void in Random 3‑SAT

Read full text
Authors: Radu-Daniel Derscariu
Cited by: 4
References: 5

Abstract

We report the experimental discovery of a universal, persistent second Betti number β₂ > 0 in the continuous low‑energy subspace of random 3‑SAT. By sampling points from the continuous relaxation [0,1]ⁿ that violate at most one clause (energy ≤ 1) and computing their Vietoris–Rips homology, we find that β₂ > 0 for every tested instance at all clause densities α ∈ [2.0, 4.5] and for system sizes n up to 12. This "continuous void" is a permanent geometric feature of the solution landscape, independent of the Boolean satisfiability regime. We further show that, at accessible system sizes (n ≤ 8), the continuous void does not correlate with the computational cost of a systematic DPLL solver (Spearman ρ ≈ −0.36 at n = 8), precisely because a persistent k‑dimensional hole requires at least k+1 ambient dimensions to act as an algorithmic obstacle. This finding is consistent with the geometric principle established in earlier work and with the picture of an emergent topological barrier in the thermodynamic limit. We also measure the "Gabriel ratio" (total topological complexity over solution volume), which collapses at the critical threshold, and perform a fine‑scale sweep of the overlap distribution, revealing a sharp condensation transition accompanied by the onset of the Overlap Gap Property. These results provide strong experimental evidence that the one‑step replica symmetry breaking (1RSB) picture correctly describes random 3‑SAT at the critical point and that the missing step for a rigorous proof of P ≠ NP is the extension of the 1RSB theorem from NAE‑SAT to canonical 3‑SAT.

Fields of Study & Subjects

Topological and Geometric Data Analysis Constraint Satisfaction and Optimization Homotopy and Cohomology in Algebraic Topology

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
6 May 2026
Document type
Preprint