This question may have an obvious answer ... but here's the question anyway. Intuitively, it is the following plausible statement - "a machine with a subroutine A which in turn has a subroutine B is the same as a machine with a subroutine A which has access to subroutine B".

To define this problem formally, I'll use some unconventional notation. When I say $A^B$, I am giving $A$ an oracle for a $B-Complete$ problem. e.g $NP^{NP}=NP^{SAT}=\Sigma_2$. With this "new" notation, it's possible to define $A^{B^C}$, and so on. My question is, is

  • is this a valid way of thinking about oracles?
  • is $(A^B)^C = A^{(B^C)}$

For example, $(NP^{NP})^{NP} = \Sigma_2^{NP} = NP^{\Sigma_2}=NP^{({NP}^{NP})}$

I can't think of any obvious counterexamples to this rule. Anyone?

  • $\begingroup$ Have you seen my question: cstheory.stackexchange.com/q/972/873? $\endgroup$ Commented Oct 26, 2010 at 17:30
  • 1
    $\begingroup$ this is a slightly more general question, but Sadeq's question is quite relevant, and especially the comments about the ill-formed-ness of A^B^C if A^B is not a computational model $\endgroup$ Commented Oct 26, 2010 at 17:43
  • $\begingroup$ no, but that was the exact thing I was hitting my head on the wall last night about which motivated this question! $\endgroup$
    – gabgoh
    Commented Oct 26, 2010 at 17:49
  • $\begingroup$ Also see this question. $\endgroup$
    – Kaveh
    Commented Oct 27, 2010 at 1:41

2 Answers 2


As Venkat told in comments, it seems hard to understand your definition for oracle which aren't defined as some machine characterisation.

Let $A^{(B^C)}$ would be the set of TM in $A$ with an oracle which is a machine in ($B$ with an oracle in a machine in $C$). It is obvious that a machine in $A$ can call $C$: it just calls the machine in $B$ and asks it to carry the message directly to $C$.

I guess ${(A^B)}^C$ would be a machine in $A$ that can call an oracle in $C$ or an oracle which is (a machine in $B$ that can call a machine in $C$) so it's exactly the same definition.

Finally, you may want $A^{B,C}$, which is certainly different from the other two (just take $B=C=NP$ and $A=P$, then $A^{B,C}=NP\cup coNP$ whereas $A^{(B^C)}=\Sigma_2^P\cup\Pi_2^p$.

  • 4
    $\begingroup$ Be careful: P^NP includes NP∪coNP, but it is not known or believed to be equal to NP∪coNP. Similarly, P^(NP^NP) is not known to be equal to Σ2P∪Π2P. $\endgroup$ Commented Oct 26, 2010 at 23:00
  • 1
    $\begingroup$ @Tsuyoshi, thank you for the remark, I don't know why I thought this. In fact if $NP\not=coNP$ it is clear that $P^{NP}$. Let $A$ and $B$ be NPcomplte and coNPcomplete problems, then the problem which take input $(x,y)$ and answer true if $x\in A$ and $y\in B$ is in $P^{NP}$ but not in $NP\cup coNP$. $\endgroup$ Commented Oct 28, 2010 at 15:26

I would write the following as a comment, but it was too long to fit in.

Let's first describe the meaning of “algorithms in class $\bf C$ with an oracle for a language A.” (The need for this was pointed out by Tsuyoshi Ito). We will use the same convention used by Ladner and Lynch. The convention is well-described by Bennett & Gill:

$\bf{LOGSPACE}^A$ can be defined in various ways, depending on how the query tape is handled. We follow the conventions of Ladner and Lynch [LL]: The query tape is not charged against the space bound, but to keep it from being used as a work tape, the query tape is one-way and write-only, and is erased automatically following each query. (Simon [Si] treats the query tape as one of the work tapes, a two-way read/write tape that is charged against the space bound. The Ladner-Lynch definition is less restrictive and perhaps more natural, since for a random oracle $A \in \bf{LOGSPACE}^A$ holds with probability 1 for [LL] but not for [Si])

[LL] R. E. LADNER AND N. A. LYNCH, Relativization of questions about log space computability, Math. Systems Theory, 10 (1976), pp. 19-32.

[Si] J. SIMON, On Some Central Problems in Computational Complexity, Tech. Rep TR 75-224, Dept. of Computer Science, Cornell University, Ithaca, NY, 1975.

The standard definition of complexity classes of oracle machines is as follows: Let B and C be complexity classes. Then, $X = B^C$ is a legitimate complexity class, defined as $X = \bigcup_{L\in C}{B^L}$. Here, $B^L$ represents the complexity class of decision problems solvable by an algorithm in class B with an oracle for a language L.

Since X is a legitimate complexity class, for any complexity class A, we can speak of complexity classes $A^X = A^{(B^C)}$ and $X^A = (B^C)^A$.

  • $A^X$ refers to the complexity class of decision problems solvable by an algorithm in class A with an oracle for any language $L' \in X = \bigcup_{L\in C}{B^L}$. In other words, $A ^ X = \bigcup\limits_{L'\in \{\bigcup\limits_{L\in C}{B^L}\}}{A^{L'}}$.

  • $X^A$ refers to the complexity class of decision problems solvable by an algorithm in class $X = \bigcup_{L\in C}{B^L}$ with an oracle for any language $L' \in A$. In other words, $X ^ A = \bigcup_{L' \in A} {{X^{L'}}} = \bigcup_{L' \in A} {{{\left( {\bigcup_{L \in C} {{B^L}} } \right)}^{L'}}}$.

Claim: $(B^{L_1})^{L'} \cup (B^{L_2})^{L'} = (B^{L'})^{L_1 \cup L_2}$.

Side Note: Since it's 3:00 AM now, I'm too sleepy to check the validity of the above claim! I think it's valid & elementary to prove, yet it's nice to see the actual proof.

Therefore, one can write $X ^ A = \bigcup_{L' \in A} {{{\left( {\bigcup_{L \in C} {{B^L}} } \right)}^{L'}}} = \bigcup_{L \in C, L' \in A} {{{\left( B^{L'} \right)}^L}}$.


Let $\bf X = \bf{P^{NP}}$. We know that $\bf{coNP} \subseteq \bf X$. Giving both sides oracle access to $\bf {NP}$, one gets: $\bf{coNP^{NP}} \subseteq \bf{X^{NP}} = (\bf{P^{NP}})^{\bf{NP}}$.


A fruitful discussion with Tsuyoshi Ito revealed (for me) that it is not easy to doubly relativize a complexity class. In fact, even defining one seems to be problematic. I should definitely study more to see if any satisfactory definition is ever given. Meanwhile, I appreciate any comment which can be used to solve this problem.

  • 4
    $\begingroup$ As I commented on another question, “algorithm in class B with an oracle for a language L” does not have a universally accepted definition in general. $\endgroup$ Commented Oct 27, 2010 at 0:11
  • $\begingroup$ @Tsuyoshi: I edited the answer to represent which definition I'm using. Does it remove the ill-formed-ness? $\endgroup$ Commented Oct 27, 2010 at 5:24
  • $\begingroup$ No. The added part only defines what LOGSPACE^A means, not what B^A means for something like B=NP^NP. $\endgroup$ Commented Oct 27, 2010 at 5:31
  • $\begingroup$ @Tsuyoshi: Thanks. I just added an example to clarify what I mean. I want a definition such that if $A \subseteq X$, then $A^C \subseteq X^C$ (A very natural requirement). Can you help me figure out how this must be defined when X is an oracle class, like NP^NP? $\endgroup$ Commented Oct 27, 2010 at 5:37
  • 4
    $\begingroup$ Unfortunately, your “natural requirement” is in fact not so natural. Although PSPACE⊆IP and there is a natural and widely accepted definition of IP^A for any language A (the verifier is given an oracle access to A), it is known that PSPACE^A⊈IP^A with probability 1 for a random oracle A; see Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan and Rohatgi 1994. As I said, there is not a widely accepted definition of C^A for an arbitrary complexity class C as far as I know. (more) $\endgroup$ Commented Oct 27, 2010 at 5:57

Your Answer

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

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