[FOM] P vs NP undecidability?

Alasdair Urquhart urquhart at cs.toronto.edu
Mon Nov 3 11:11:55 EST 2003


In reply to Vladimir Sazonov's query:

It's true that Okamoto and Kashima use
an asymptotic notion of provability.
However, they seem quite clearly to 
state that their result implies that
"P=NP" is consistent with Peano 
Arithmetic.  In fact, they go further,
since they say on p. 36 that:
"There exists no formal proof of "P \neq NP"
in any reasonable theory."  

In the introductory section 1.2, they say that 
"P = NP" is consistent with any omega-consistent
extension of Peano arithmetic.  If they had 
really proved that claim then they certainly 
would have proved that P=NP.







More information about the FOM mailing list