Inductive Complexity of P versus NP Problem Extended Abstract
Cristian S. Calude, Elena Calude, Melissa S. Queen · 2012
Using the complexity measure developed in (7,3,4) and the extensions obtained by using inductive register machines of various or- ders in (1,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 more complex than the Riemann hypothesis.