[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