18.4CCMay 24
Constructibility and the P versus NP problemArne Hole
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.