INDUCTIVE COMPLEXITY OF THE P VERSUS NP PROBLEM
Abstract
This paper does not propose a solution, not even a new possible attack, to the P versus NP problem. We are asking the simpler question: How “complex” is the P versus NP problem? Using the inductive complexity measure—a measure based on computations run by inductive register machines of various orders—developed in [2], we determine an upper bound on the inductive complexity of second order of the P versus NP problem. From this point of view, the P versus NP problem is significantly more complex than the Riemann hypothesis. To date, the P versus NP problem and the Goostein theorem (which is unprovable in Peano Arithmetic) are the most complex mathematical statements (theorems, conjectures and problems) studied in this framework [9, 5, 6, 2, 20].
An extended abstract of this paper has appeared in J. Durand-Lose, N. Jonoska (eds.). Proceedings UCNC 2012, LNCS 7445, Springer, (2012), 2–9.


