[FOM] P vs NP undecidability

Alasdair Urquhart urquhart at cs.toronto.edu
Thu Oct 30 16:33:10 EST 2003

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).  
However, the only properties of PA that seem to be
used in the proof are:

1.  PA is omega-consistent;
2.  All poly-time functions are representable in PA (Thm 9);
3.  Proofs in PA are poly-time checkable.

Let us assume that the claim that I just made is 
correct (that is to say, these are in fact the
only key properties used).  Then if (P \neq NP) is true, 
PA + (P \neq NP) has the above three properties.
It follows that the paper proves that P = NP.
This makes me very sceptical of its correctness.

Alasdair Urquhart

More information about the FOM mailing list