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

[Lasse Rempe]

姚鹏晖 wrote:
> Solovay proved the theorem:
>   There is an oracle A such that P relative to A do not equal to NP relative A.
>
> If B and C are two complexity classes and B=C,  does B still equal  to
> C relative to any oracle?
No.

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.

-- 
-------------------------------------------
Dr. Lasse Rempe
Dept. of Math. Sciences, Univ. of Liverpool
Liverpool, L69 7ZL, United Kingdom
Office 505, Tel. +44 (0)151 794 4058  
L.Rempe at liverpool.ac.uk
http://pcwww.liv.ac.uk/~lrempe
-------------------------------------------