[FOM] P=NP and complexity

[Alasdair Urquhart]

As for the Baker-Gill-Solovay oracle
results, I am not sure whether I would
draw the conclusion that James Cummings drew,
namely that the P=NP question is one of
combinatorics rather than recursion theory.

My point is more: what are we to make of these
results?  In some sense, they do show that
no simple arguments of a certain type will
work.  But what do we mean by "simple arguments
of a certain type"?  In the complexity theory
literature, the results are often discussed as
if they are independence results, which they
are not.  

Is there some way to make precise *logically* 
what we mean by "relativizable arguments"?
I consider this a major open question.

FOM readers who are interested in these questions
may like to read the thoughtful article
"Circuit Complexity Before the Dawn of the New 
Millenium" by Eric Allender.  It is available
for download on his web site.

Alasdair