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

姚鹏晖 phyao1985 at gmail.com
Fri Mar 2 05:39:48 EST 2007


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?


More information about the FOM mailing list