Сохранить в:
| Главный автор: | |
|---|---|
| Формат: | Recurso digital |
| Язык: | |
| Опубликовано: |
Zenodo
2025
|
| Предметы: | |
| Online-ссылка: | https://doi.org/10.5281/zenodo.15087349 |
| Метки: |
Добавить метку
Нет меток, Требуется 1-ая метка записи!
|
Оглавление:
- <h3>A Formal Resolution of the P vs NP Problem via Entropy Barriers, Compression Limits, and Non-Relativizing Structural Complexity</h3> <p>This paper presents a mathematically rigorous proof that the complexity classes P and NP are not equal. The approach integrates entropy theory, instance compression, and circuit complexity to demonstrate that no deterministic polynomial-time algorithm can decide all NP-complete problems.</p> <p>The proof begins by establishing an entropy barrier, showing that any attempt to distinguish among exponentially many valid solutions with polynomially bounded resources results in an information-theoretic contradiction. A compression impossibility theorem is introduced to show that instances of NP-complete problems cannot be reduced to polynomial length while preserving solvability, violating known bounds on Kolmogorov complexity.</p> <p>Additionally, the paper demonstrates that solving NP-complete problems requires superpolynomial circuit size, and that no uniform or nonuniform polynomial-sized family of algorithms can bypass this requirement. The entire argument is non-relativizing, meaning it remains valid regardless of oracle access or relativized computational models.</p> <p>A section is also dedicated to the limits of quantum computing, clarifying that quantum algorithms cannot collapse NP into P due to fundamental constraints on state representation and computational entropy.</p> <p>The result is a complete and modular proof that P does not equal NP, resolving one of the most significant open questions in theoretical computer science.</p>