Uloženo v:
| Hlavní autor: | |
|---|---|
| Médium: | Recurso digital |
| Jazyk: | |
| Vydáno: |
Zenodo
2026
|
| Témata: | |
| On-line přístup: | https://doi.org/10.5281/zenodo.20051442 |
| Tagy: |
Přidat tag
Žádné tagy, Buďte první, kdo vytvoří štítek k tomuto záznamu!
|
Obsah:
- <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>