[FOM] why don't Solovay's theorem implies P!=NP?

[Timothy Y. Chow]

Lasse Rempe <L.Rempe at liverpool.ac.uk> wrote:
> It is known, e.g. that IP = PSPACE; however, IP \neq PSPACE with respect 
> to "almost all" oracles. Similarly, I am pretty sure that the famous PCP 
> theorem does not hold with respect to all oracles. I believe 
> Papadimitriou's book has a discussion and references. Others will be 
> better informed than me, and may be able to point to more specific 
> references.

The PCP theorem indeed does not relativize.  A pretty good reference for 
this kind of question is Lance Fortnow's paper "The role of relativization 
in complexity theory," which can be easily found on the web.

But probably the original question stems from a more basic confusion, 
which is unfortunately encouraged by the standard notation for oracles, 
according to which one writes things such as "P^A = NP^A".  Namely, this 
notation might suggest that what you're doing is you're starting with the 
*set of languages* P and the *set of languages* NP, and doing something to 
each set.  Moreover, it seems to suggest that whatever it is you're doing 
to the two sets, it's the "same thing," in the sense that if you start 
with the same set on both sides then you must end up with the same set on 
both sides.

This, of course, is *not* what is going on.  One is not manipulating the 
set of languages directly, but manipulating the *model of computation* 
that is giving rise to the set of languages.  So it's possible to start 
with two different models of computation that "happen" to produce the same 
set of languages, and tinker with the two models in a highly analogous 
way, yet wind up with two models of computation that produce different 
languages.

I often wonder if there are some simple and fruitful ideas in this area 
that have gone overlooked because of the psychologically misleading 
notation for oracles that everyone uses.

Tim