[FOM] P vs NP undecidability

Vladimir Sazonov V.Sazonov at csc.liv.ac.uk
Fri Oct 31 12:26:01 EST 2003

Alasdair Urquhart wrote:
> I've studied the paper by Okamoto and Kashima,
> and I am quite sceptical about its correctness.
> The authors claim to show that "P=NP" is consistent
> with Peano Arithmetic (Theorem 38, p. 37).

As I understood they are using some unusual concept of 
"asymptotic" provability. (Am I right?) Thus, the meaning 
of the symbol |- and of the result may be quite different 
than it looks... I found this paper difficult to read, 
at least with the lack of time. 

Vladimir Sazonov

More information about the FOM mailing list