Experimental Detection of the Overlap Gap Property in Random 3‑SAT and a Novel Graph‑Theoretic Complexity Metric

We present a new experimental framework for the geometric analysis of solution spaces of Boolean satisfiability (SAT) problems. By extending the solution space with a third logical state (uncertainty) based on Kleene's strong three-valued logic (1938), we define a graph‑theoretic density metric (circuit rank, denoted β₁) that sharply separates 2‑SAT from 3‑SAT with a difference of 2–3 orders of magnitude, on 150 planted instances (n=8−12). We show that this metric primarily measures solution density, not computational difficulty (negligible correlation with industrial solver runtime, tested preliminarily). At the critical threshold (α=4.2), we observe a statistically significant bimodal distribution of Hamming distances between Boolean solutions, a pattern consistent with the Overlap Gap Property (OGP) — an algorithmic barrier rigorously proven in the literature (Gamarnik & Sudan, 2021). We define an extended metric, Topological Complexity Density (TCD), based on the clique complex of the extended Hamming graph, and show that the ratio TCD(3‑SAT)/TCD(2‑SAT) grows significantly as the number of allowed intermediate dimensions increases. We also perform a preliminary test of the Valiant reduction on a micro‑instance, whose circuit rank drops from 11 to 0. Our results provide the first experimental evidence consistent with OGP on canonical 3‑SAT at α=4.2 and suggest that TCD is a promising measure for investigating structural differences between complexity classes. Updated version (v2): added extended experimental data on Branching OGP (BOGP), Franz-Parisi potential, OGP universality table, selective barrier analysis (Belief Propagation/Survey Propagation vs. Kissat/WalkSAT), and a sharp-threshold scan. Corrected minor bibliographic details.