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$!

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

It's worth mentioning that relativization to oracles is not, strictly speaking, an operation on a class of languages but rather on the computational models that accept those languages. When resource consumption is an issue, as it is in complexity theory, the construction is sensitive to the details of computational models, and different models can give different classes of languages when relativized.

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.

  • $\begingroup$ Okay, thanks! Also relevant I think: this $\endgroup$ – 6005 Nov 18 '15 at 6:34
  • $\begingroup$ You're welcome. And that other page certainly is relevant too. $\endgroup$ – BrianO Nov 18 '15 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.