Constructibility and the P versus NP problem
arXiv:2406.1684318.4h-index: 27
Predicted impact top 62% in CC · last 90 daysOriginality Incremental advance
AI Analysis
For complexity theorists, it provides a limitation on the provability of P = NP within certain formal systems.
The paper addresses the P versus NP problem by showing that no constructible, arithmetically sound, and formalizable theory can prove P = NP, under natural conditions on the definition of constructible theory.
The P versus NP problem is addressed in a context of provability and limitations on the possibility of finding sound axioms for formal theories. It is shown that if the term "constructible theory" is defined in a way which satisfies certain natural conditions, then no constructible, arithmetically sound and formalizable theory proves P = NP.