FOM: Independence of "P=NP"?

[Alasdair Urquhart]

The independence of the major questions
of complexity theory from PA or even ZFC is of
course a tempting conjecture, given the failure
to settle them in spite of intensive research extending
over the last 30 years.  Nevertheless, I think it is fair
to say that the evidence in favour of this idea is
so far quite slight.  Work on systems of bounded arithmetic
has supplied a small amount of evidence in this direction,
but these systems are very weak even compared
with primitive recursive arithmetic, since (for example)
it is impossible to demonstrate the totality of the
function 2^n in them.  Nevertheless, work is continuing along
these lines; a lot of talented researchers are working on
these problems, but so far progress has been slow.

An attempt at proving consistency of "P = NP" by Newton da Costa
and Francisco Doria was posted to the Los Alamos preprint server
as math.LO/0006079.  It contains some interesting ideas, but
was subjected to what appeared to be devastating criticism by 
Ralf Schindler in a follow-up article on the same server
(math.LO/0007025).    I have not seen any satisfactory reply
to Schindler's criticism, and I doubt that any such reply is
possible, given the fundamental nature of the objections.

Alasdair Urquhart