Are any $A$, $B$, and $O$ such that:

  • $O$ is a set (for oracle),
  • $A$ and $B$ are the names of two known complexity classes,
  • $A^X$ and $B^X$ have well-defined accepted meanings,
  • $A=A^\emptyset\subset B^\emptyset=B$, i.e. $A$ is strictly contained in $B$,
  • $A^O\supset B^O$, i.e. $A^O$ strictly contains $B^O$.

In the case of $\mathsf{P}$ and $\mathsf{EXP}$, it's impossible to find an oracle $O$ relative to which $\mathsf{P}^O$ strictly contains $\mathsf{EXP}^O$ since a $\mathsf{EXP}^X$ can completely simulate every step of any turing machine in $\mathsf{P}^X$ (i.e. the time hierarchy theorem relativizes).

I'm wondering if there are complexity classes $A$, $B$ s.t. $A \subset B$, yet for some oracle $O$, $A^O \supset B^O$. In other words, can the direction of strict inclusion change when complexity classes are relativized?

  • $\begingroup$ Since you wrote “in the most general case,” what is your definition of “complexity class”? $\endgroup$ Commented Jan 29, 2013 at 3:08
  • 3
    $\begingroup$ Also note that there are more than one definition for space-bounded complexity classes in a relativized world, depending on whether you count the oracle tape as part of space or not. “Take a complexity class, and attach an oracle” is not a nice operation because we are usually using different oracle models e.g. when we talk about L^O (where the oracle tape usually does not count towards the space complexity) and when we talk about PSPACE^O (where the oracle tape usually counts towards the space complexity). I think that there was a recent question related to this point…. $\endgroup$ Commented Jan 29, 2013 at 3:54
  • 2
    $\begingroup$ It is the other way around. P^HALT ⊊ EXP^HALT, and as I said, it is just the time hierarchy theorem. $\endgroup$ Commented Jan 29, 2013 at 12:46
  • 3
    $\begingroup$ Not all classes on the complexity zoo admit oracles: what would $CFL^O$ mean? $\endgroup$
    – Max
    Commented Jan 29, 2013 at 14:49
  • 5
    $\begingroup$ The zoo used to display a warning sign reading “Please do not feed oracles to the complexity classes! These classes require a specially balanced diet to ensure proper relativization.” Unfortunately, it seems to be gone (or well hidden) in its Wiki reincarnation. $\endgroup$ Commented Jan 29, 2013 at 17:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.