The OGP as an Informational Filter: Experimental Evidence for a Universal Binary Barrier in NP‑Complete Problems

We present comprehensive experimental evidence that the Overlap Gap Property (OGP) functions as an informational filter rather than a gradual computational barrier. Across 9 experimental contexts— 8 canonical NP-complete problems (3-SAT, NPP, MAX-CUT, MIS, NAE-3-SAT, SBM, Planted Clique, Symmetric Binary Perceptron) plus a novel Collision OGP setting—and 7 major classes of algorithms (message passing, low-degree polynomials of degree 1–2, low-degree polynomials of degree 3, simulated annealing, Langevin dynamics, WalkSAT, and CDCL), we find that OGP acts as a binary barrier: it completely annihilates any algorithm that attempts to make globally coherent decisions based on an integrated picture of the solution space (BP, SP: 0% success; low-degree polynomials degree 1–2: ∼15% success), yet leaves purely local, exploratory algorithms completely unaffected (WalkSAT, SA, Langevin: 100% success). Crucially, the barrier activates instantaneously and totally: even a 10% fraction of variables flipped simultaneously based on global BP marginals is sufficient to cause 100% failure. These results refine the Computational Black Hole Conjecture: the OGP does not block all polynomial-time algorithms, but it blocks all algorithms that rely on globally coherent, integrated information—a class that arguably includes any algorithm capable of solving NP-complete problems in the worst case. We provide a complete experimental roadmap and identify the single remaining theoretical step to proving P ̸= NP