محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | Recurso digital |
| اللغة: | |
| منشور في: |
Zenodo
2026
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://doi.org/10.5281/zenodo.20103979 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
جدول المحتويات:
- <p>We present a complete conditional proof that P ̸= NP by reducing the problem to a single, well-defined Reduction Conjecture. First, we establish that canonical random 3-SAT at clause density α = 4.2 belongs to the one-step replica symmetry breaking (1RSB) universality class, extending the Nam–Sly–Sohn framework. The 1RSB condensation implies the Overlap Gap Property (OGP), persistent topological voids (β2 > 0), and macroscopic free-energy barriers. Second, we prove the Black Hole Trilemma: any polynomial-time algorithm for this problem must be either global (blocked by the OGP), systematic (blocked by exponential backtracking from β2 > 0), or local (blocked by exponentially slow mixing). Third, we formulate the Reduction Conjecture: any algorithm that uses global information about the solution space can be simulated by a Statistical Query (SQ) algorithm, and therefore fails when the Franz–Parisi potential is strictly positive. We provide strong theoretical justification for the conjecture via the transfer principle of Jones et al. and the SQ/low-degree equivalence of Brennan et al., as well as direct experimental evidence showing that low-degree predictability collapses to zero at the critical density. Under the Reduction Conjecture, the Black Hole Trilemma covers all remaining cases, and P ̸= NP follows unconditionally. All other components are rigorously proved either in the literature or in the author’s prior work.</p>