4
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • $\begingroup$ Since you wrote “in the most general case,” what is your definition of “complexity class”? $\endgroup$
    – Tsuyoshi Ito
    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$
    – Tsuyoshi Ito
    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$
    – Tsuyoshi Ito
    Jan 29, 2013 at 12:46
  • 3
    $\begingroup$ Not all classes on the complexity zoo admit oracles: what would $CFL^O$ mean? $\endgroup$
    – Max
    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$
    – Emil Jeřábek
    Jan 29, 2013 at 17:45

0

Reset to default

Your Answer

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