Addendum 8 v2: Rigorous Exponential Backtracking from the Persistent Topological Void (Size–width trade‑off for the 1‑RSB solution space)
Fuente:
Zenodo
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Recurso digital |
| Veröffentlicht: |
Zenodo
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866901756006367232 |
|---|---|
| author | Derscariu, Radu-Daniel |
| author_facet | Derscariu, Radu-Daniel |
| contents | <p>We prove that the persistent 2‑dimensional void β₂ > 0 in the Vietoris–Rips complex of the solution space of the Poisson‑cloned 3‑SAT model at clause density α = 4.2 (Addendum 7 v2) forces any resolution refutation to have exponential size. Consequently, any systematic backtracking algorithm (DPLL, CDCL) requires exponential time on random 3‑SAT at the critical density. This completes the third and final obstruction of the Black Hole Trilemma: global algorithms are blocked by the Overlap Gap Property (Addendum 6 v2), local algorithms are blocked by exponential mixing (Addendum 4 v2), and systematic algorithms are blocked by exponential backtracking. The final theorem P ≠ NP follows as described in Addendum 9.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_20051442 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Addendum 8 v2: Rigorous Exponential Backtracking from the Persistent Topological Void (Size–width trade‑off for the 1‑RSB solution space) Derscariu, Radu-Daniel exponential backtracking resolution size-width tradeoff 3-SAT 1RSB Black Hole Trilemma <p>We prove that the persistent 2‑dimensional void β₂ > 0 in the Vietoris–Rips complex of the solution space of the Poisson‑cloned 3‑SAT model at clause density α = 4.2 (Addendum 7 v2) forces any resolution refutation to have exponential size. Consequently, any systematic backtracking algorithm (DPLL, CDCL) requires exponential time on random 3‑SAT at the critical density. This completes the third and final obstruction of the Black Hole Trilemma: global algorithms are blocked by the Overlap Gap Property (Addendum 6 v2), local algorithms are blocked by exponential mixing (Addendum 4 v2), and systematic algorithms are blocked by exponential backtracking. The final theorem P ≠ NP follows as described in Addendum 9.</p> |
| title | Addendum 8 v2: Rigorous Exponential Backtracking from the Persistent Topological Void (Size–width trade‑off for the 1‑RSB solution space) |
| topic | exponential backtracking resolution size-width tradeoff 3-SAT 1RSB Black Hole Trilemma |
| url | https://doi.org/10.5281/zenodo.20051442 |