Technical Addendum to "A Conditional Proof that P ≠ NP": Detailed Proof Plan for the 1RSB Extension

Indexed indatacite

Abstract

This addendum provides the technical details required to extend the one-step replica symmetry breaking (1RSB) proof of Nam, Sly & Sohn (2021/2024) from random regular NAE-SAT to canonical 3-SAT at clause density α = 4.2. It pinpoints the precise points in the existing proof where the symmetry of NAE-SAT is exploited, shows how to replace the uniform Fourier analysis with p-biased Fourier analysis, sketches the Guerra–Toninelli interpolation adapted to 3-SAT hypergraphs, and outlines the FKCK percolation mapping that yields a persistent second Betti number β2 > 0. The chain of lemmas constituting the final proof is stated explicitly.

Citation impact

30
total citations
FWCI
Percentile
References
2
Too recent for citation history.

Authors

1

Topics & keywords

Keywords
  • Addendum
  • Mathematical proof
  • Interpolation (computer graphics)
  • Extension (predicate logic)
  • Symmetry (geometry)
  • Proof of concept
  • Replica
  • Proof theory
No related works found for this paper.