Addendum 6: Overlap Concentration and the Overlap Gap Property
Abstract
We show that the convergence of the free energy to the 1RSB prediction (established in Addenda 4 and 5) implies that the overlap distribution P (q) of two random solutions concentrates on exactly two values q0 < q1. This directly yields the Overlap Gap Property (OGP): with high probability, no two solutions have overlap in the interval (q0, q1). The result follows from standard arguments in spin-glass theory (Panchenko 2013) adapted to the 3-SAT setting
Fields of Study & Subjects
Theoretical and Computational Physics
Complex Systems and Time Series Analysis
Random Matrices and Applications
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 6 May 2026
- Document type
- Preprint