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)

Read full text
Authors: Radu-Daniel Derscariu
Cited by: 2
References: 9

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