Ill-Defined Complexity at the SAT Phase Transition Runtime Distributions and the Limits of Polynomial Bounds

Read full text
Authors: HIDEYUKI CHINO
Cited by: 0

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