INDUCTIVE COMPLEXITY OF THE P VERSUS NP PROBLEM.

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]. [ABSTRACT FROM AUTHOR]