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

Ignacio Nattochdag inattochdag at gmail.com
Tue Mar 6 11:35:45 EST 2007


On 3/2/07, 姚鹏晖 <phyao1985 at gmail.com> 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?

Not necessarily: there are oracles with P = NP and oracles with P
different from NP; this was established by Solovay himself and others:
see "Relativizations of the P = NP question, SIAM journal of
computing".

I. Nattochdag



More information about the FOM mailing list