Сохранить в:
| Главный автор: | |
|---|---|
| Формат: | Recurso digital |
| Язык: | |
| Опубликовано: |
Zenodo
2025
|
| Предметы: | |
| Online-ссылка: | https://doi.org/10.5281/zenodo.15088639 |
| Метки: |
Добавить метку
Нет меток, Требуется 1-ая метка записи!
|
Оглавление:
- <p>This paper presents a complete and rigorous proof that P is not equal to NP, resolving one of the most fundamental open problems in theoretical computer science. The proof integrates three independent approaches: an entropy-based decision tree complexity barrier, a compression impossibility theorem grounded in Kolmogorov complexity, and a non-relativizing circuit complexity separation. Together, these demonstrate that NP-complete problems cannot be solved in polynomial time by any deterministic algorithm.</p> <p>The entropy argument shows that distinguishing among all possible solutions requires an exponential number of steps. The compression theorem proves that no polynomial-time function can reduce an NP-complete instance to a smaller equivalent form while preserving decidability. The circuit complexity result establishes that solving NP-complete problems requires circuits of exponential size, beyond the scope of polynomial-time computation.</p> <p>These results hold universally, even under oracle and quantum models, making the separation between P and NP robust across computational paradigms. The proof draws from foundational principles in complexity theory, including Shannon entropy, Kolmogorov complexity, and structural bounds from circuit lower bounds literature.</p> <p>This work has significant implications for cryptography, optimization, computational hardness, and our broader understanding of algorithmic limits.</p>