I posted a paper about my solution to the P/NP problem on arXiv this week: arXiv:1104.2538v1 The key idea making this paper different from other approaches is that the relationship between the complexity classes P and NP depends on the definition of the natural numbers. In other words, there is no clear answer to the P/NP problem. The paper claims that for the traditional encoding of the natural numbers, which is based on the Peano axioms, the complexity hierarchy collapses and P becomes equal to NP. On the other hand, if we remove the first Peano axiom, P becomes a proper subset of NP.

The removal of the first Peano axiom introduces intrinsic uncertainty into the encodings of natural numbers, which obviously has drastic consequences on computability and computational complexity. Every computation, and every proof, is uncertain under this relaxed set of Peano axioms. However, the first Peano axiom cannot remove this uncertainty, it can merely subsume it into one statement. I think this fact and the consequences it has on computational complexity has been underestimated in the literature so far. I’m going to elaborate more on this here in the coming months.