[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