[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