Ill-Defined Complexity at the SAT Phase Transition Runtime Distributions and the Limits of Polynomial Bounds
Abstract
This manuscript reexamines the P versus NP problem from a structural and conceptual perspective. Instead of addressing the problem as a purely technical question of algorithmic efficiency, the paper frames P=NP as an instance of criticality arising from fixed representational assumptions in computational complexity theory. By drawing analogies with phase transitions and convergence phenomena, the work argues that the persistence of the P=NP problem reflects limitations in how computational questions are formulated, rather than a lack of computational ingenuity. This manuscript is currently under review at Foundations of Physics.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Computability
Logic
AI Algorithms
Advanced Graph Theory Research
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 19 January 2026
- Language
- EN
- Document type
- Preprint