A TOPOLOGICAL BARRIER FOR AVERAGE-CASE RANDOM 3-SAT: NON-COLLAPSE OF THE BACKBONE FILTRATION SPECTRAL SEQUENCE VIA AN EXPLICIT FRUSTRATION GADGET

Read full text Summarise with VIRAT
Authors: Leo Kim, Sergey Kim
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Abstract We prove that the backbone filtration spectral sequence of the cubical search complex K(φ) for a specific 3-variable, 6-clause 3-SAT instance — the frustration gadget φG — does not collapse at E2. Specifically, d2 ≠ 0 in the backbone filtration of the correct-backbone subcomplex K+(φG). The proof is a clean rank argument: K+(φG) has 12 vertices, 20 edges, 0 squares, homology H1 = ℤ9, while the spectral sequence abutment can contribute at most rank 4 to degree 1 (since E1 2,0 has total degree 2 and contributes to H2, not H1); the contradiction 9 > 4 forces d2 ≠ 0. All computations are verified by a 60-line Python script. We then embed this result in a broader conditional framework: under the 1-RSB cavity-method prediction that random 3-SAT at m/n =4.267 contains Ω(n) disjoint copies of φG (rigorous for large k [13, 23], conjectured for k = 3 [11,19]), the spectral sequence of K(φn) does not degenerate at E2. We do not claim to resolve P vs NP; the unconditional contribution is the explicit minimal gadget proof.

Fields of Study & Subjects

Constraint Satisfaction and Optimization Advanced Graph Theory Research Complexity and Algorithms in Graphs

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
22 March 2026
Language
EN
Document type
Preprint