Addendum 8: Exponential Backtracking from the Persistent Topological Void

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

Abstract

We prove that the persistent 2-dimensional void β2 > 0 in the solution space of random 3-SAT at α = 4.2 (Addendum 7) forces any resolution refutation to have exponential size. This, in turn, implies that any systematic backtracking algorithm (DPLL, CDCL) requires exponential time. Together with the Overlap Gap Property (blocking global algorithms, Addendum 6) and the exponential mixing barrier (blocking local dynamics, Addendum 4), all three obstructions of the Black Hole Trilemma are now established. The final addendum (Addendum 9) will state the theorem P ̸= NP.

Fields of Study & Subjects

Topological and Geometric Data Analysis Markov Chains and Monte Carlo Methods Computational Geometry and Mesh Generation

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
6 May 2026
Document type
Preprint