5

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • Since you wrote “in the most general case,” what is your definition of “complexity class”? – Tsuyoshi Ito Jan 29 '13 at 03:08
  • @TsuyoshiIto: good point. Anything in the complexity zoo is fair game. –  Jan 29 '13 at 03:18
  • About the section labelled as “Related”: (1) It is better to avoid using L because L is the name of a well-known complexity class. I suggest HALT as your language represents the halting problem. (2) Why is P^HALT = EXP^HALT? I think that P^HALT ≠ EXP^HALT by the time-hierarchy theorem. Are there any subtleties in defining EXP^O? – Tsuyoshi Ito Jan 29 '13 at 03:33
  • 3
    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…. – Tsuyoshi Ito Jan 29 '13 at 03:54
  • @TsuyoshiIto: Changed the oracle from $L$ to $Accept$. Can you expand on why $P^{Halt}$ strictly contains $EXP^{Halt}$? –  Jan 29 '13 at 07:55
  • 2
    It is the other way around. P^HALT ⊊ EXP^HALT, and as I said, it is just the time hierarchy theorem. – Tsuyoshi Ito Jan 29 '13 at 12:46
  • 3
    Not all classes on the complexity zoo admit oracles: what would $CFL^O$ mean? – Max Jan 29 '13 at 14:49
  • 5
    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. – Emil Jeřábek Jan 29 '13 at 17:45
  • @TsuyoshiIto: Yes, but we're looking for inclusion the other way. I.e. some oracle relative to which $Big^O$ is strictly contained in $Small^O$ .... –  Jan 29 '13 at 20:45
  • In case it is not clear, the point of my comment is that your claim that P^Accept = EXP^Accept is incorrect. – Tsuyoshi Ito Jan 29 '13 at 22:19
  • @tkxue, the same argument that you use to say that the direction cannot change for P and EXP shows that they cannot be equal either. Note that the time hierarchy theorem relativizes. I made a few changes to your post, feel free to roll back my edits or edit them. – Kaveh Jan 30 '13 at 06:58
  • @Kaveh: the question looks much better now. Thanks! –  Jan 30 '13 at 08:59

0 Answers0