# Can relativization change the direction of separation?

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?

• Since you wrote “in the most general case,” what is your definition of “complexity class”? Commented Jan 29, 2013 at 3:08
• 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…. Commented Jan 29, 2013 at 3:54
• It is the other way around. P^HALT ⊊ EXP^HALT, and as I said, it is just the time hierarchy theorem. Commented Jan 29, 2013 at 12:46
• Not all classes on the complexity zoo admit oracles: what would $CFL^O$ mean?
– Max
Commented Jan 29, 2013 at 14:49
• 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. Commented Jan 29, 2013 at 17:45