# What does $\forall X: A^X \subseteq B^X$ mean?

In Greg Kuperberg's complexity zoology inclusion diagram, there is a color coding based on whether or not $$\forall X : A^X \subseteq B^X$$ is proven, disproven, or unknown.

What does this notation mean? I expect it does not mean the same thing as simple inclusion, because according to the diagram, it is known that $NP$ is not contained (in this sense) in $P$!

• It means the inclusion $A\subseteq B$ is preserved under relativization to oracles $X$. – BrianO Nov 18 '15 at 2:17
• @BrianO Great, thanks. You could make an answer (relevant links would be nice!) – 6005 Nov 18 '15 at 3:01
• OK in just a little... – BrianO Nov 18 '15 at 3:02
• Why the downvote?? – 6005 Dec 11 '15 at 3:01

Where $A, B$ and are complexity classes of languages (or problems), and $X$ is a set (/language), $A^X$ denotes the complexity class of languages accepted by Turing machines (TMs) conforming to the criteria of $A$ (e.g. log space, deterministic polynomial time), each TM augmented with the ability to use $X$ as an oracle: the machine can ask a single step whether a string on the tape is in $X$ or not, and its next state is determined by the answer. The oracle calls are single instructions, requiring just one step to compute and no additional space (beyond that required to store the inputs to the oracle). For details of how this is formalized, see this article on oracle machines.
By extension, if $\mathscr{C}$ is a complexity class, or any set of languages, the notation can be extended to encompass oracle machines with any oracle in $\mathscr{C}$: $$A^\mathscr{C} = \bigcup_{X\in \mathscr{C}} A^X.$$
The statement $\forall X\colon A^X\subseteq B^X$ therefore means, for every oracle $X$, $A^X\subseteq B^X$. Because $C^{\emptyset} = C$ for any complexity class $C$, the statement implies that $A\subseteq B$.
Perhaps contrary to initial intuition, oracles can change a basic inclusion relationship: it's possible that $A\subsetneq B$ but $A^X= B^X$ for some oracle $X$. (In fact, it's possible to have $A=B$ but $A^X\ne B^X$ for some classes $A,B$ and oracle $X$ see here or here for proofs that IP = PSPACE, and the answer here for a link to the result that the identity fails when relativized to certain oracles.) A famous result by Baker, Gill and Solovay shows that there is an oracle $X$ such that $P^X \ne NP^X$ (so $P^X\subsetneq NP^X$), and there is an oracle $Y$ such that $P^Y = NP^Y$. As discussed briefly in this wikipedia article on P=NP?, this result shows that any method of proof which remains valid when oracles are introduced ("relativizing proofs") cannot successfully solve the problem. For more on the Baker, Gill and Solovay theorem and its consequences, see these lecture notes, and this stackoverflow Q&A.