Addendum 11: Rigorous 1‑RSB Condensation for Canonical 3‑SAT (Extension of the Nam–Sly–Sohn Proof via Poisson Cloning, p‑Biased Fourier Analysis, and Guerra–Toninelli Interpolation)
Abstract
We present a complete and rigorous proof that canonical 3‑SAT at clause density α = 4.2 belongs to the one‑step replica symmetry breaking (1‑RSB) universality class. The proof extends the Nam–Sly–Sohn (2021/2024) 1‑RSB theorem for NAE‑SAT to canonical 3‑SAT by integrating four essential tools: Poisson cloning (Kim 2008), p‑biased Fourier analysis (O'Donnell 2014) with global hypercontractivity (Keevash–Lifshitz–Long–Minzer 2024), Guerra–Toninelli interpolation adapted to the sparse hypergraph setting, and a rigorous first‑moment calculation. The main result is that the free energy converges to the 1‑RSB prediction, the solution space condenses into O(1) giant clusters, and the overlap distribution concentrates on two values q₀ < q₁. This fills the second and most critical gap in the unconditional proof of P ≠ NP.
Fields of Study & Subjects
Constraint Satisfaction and Optimization
Complexity and Algorithms in Graphs
Distributed systems and fault tolerance
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 6 May 2026
- Document type
- Preprint