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

<p>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$.</p>

<p>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.</p>

<p>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$.</p>

CC BY-SA 2.5
2010-10-26T23:00:57.983Z
Be careful: [P^NP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:D#delta2p) 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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-28T15:26:47.673Z
@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$.
Arthur MILCHIOR
CC BY-SA 2.5
2010-10-26T22:25:25.593Z
2010-10-26T23:03:40.437Z
2010-10-26T23:03:40.437Z
Arthur MILCHIOR
<p>I would write the following as a comment, but it was too long to fit in.</p>

<p>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 <a href="http://www.springerlink.com/content/j1562qn040167225/" rel="nofollow">Ladner and Lynch</a>. The convention is well-described by <a href="http://dx.doi.org/10.1137/0210008" rel="nofollow">Bennett &amp; Gill</a>:</p>

<blockquote>
  <p>$\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])</p>
  
  <p>[LL] R. E. LADNER AND N. A. LYNCH, <em>Relativization of questions about log space computability</em>, Math. Systems Theory, 10 (1976), pp. 19-32.</p>
  
  <p>[Si] J. SIMON, <em>On Some Central Problems in Computational Complexity</em>, Tech. Rep TR 75-224, Dept. of Computer Science, Cornell University, Ithaca, NY, 1975.</p>
</blockquote>

<p>The standard definition of <a href="http://en.wikipedia.org/wiki/Oracle_machine#Complexity_classes_of_oracle_machines" rel="nofollow">complexity classes of oracle machines</a> is as follows: Let B and C be <strong>complexity classes</strong>. 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.</p>

<p>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$.</p>

<ul>
<li><p>$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'}}$.</p></li>
<li><p>$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'}}}$. </p></li>
</ul>

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

<p><code>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 &amp; elementary to prove, yet it's nice to see the actual proof.</code></p>

<p>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}}$.</p>

<h3>Example</h3>

<p>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}}$.</p>

<h2>Epilogue</h2>

<p>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.</p>

CC BY-SA 2.5
2010-10-27T00:11:39.920Z
As I commented on [another question](http://cstheory.stackexchange.com/questions/2490/is-p-pp-p-p), “algorithm in class B with an oracle for a language L” does not have a universally accepted definition in general.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-27T05:24:04.193Z
@Tsuyoshi: I edited the answer to represent which definition I'm using. Does it remove the ill-formed-ness?
Sadeq Dousti
CC BY-SA 2.5
2010-10-27T05:31:20.787Z
No.  The added part only defines what LOGSPACE^A means, not what B^A means for something like B=NP^NP.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-27T05:37:55.283Z
@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?
Sadeq Dousti
CC BY-SA 2.5
2010-10-27T05:57:40.953Z
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](http://dx.doi.org/10.1016/S0022-0000%2805%2980084-4).  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)
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-27T06:03:04.910Z
(cont’d)  Or course, it is possible to define (NP^NP)^A as NP^(NP^A), but if we define that way, the question “Is (NP^NP)^A equal to NP^(NP^A)?” becomes trivial.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-26T23:56:34.553Z
2010-10-27T06:05:38.090Z
2010-10-27T06:05:38.090Z
Sadeq Dousti
<p>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". </p>

<p>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</p>

<ul>
<li>is this a valid way of thinking about oracles?</li>
<li>is $(A^B)^C = A^{(B^C)}$</li>
</ul>

<p>For example, $(NP^{NP})^{NP} = \Sigma_2^{NP} = NP^{\Sigma_2}=NP^{({NP}^{NP})}$</p>

<p>I can't think of any obvious counterexamples to this rule. Anyone?</p>

CC BY-SA 2.5
2010-10-26T17:30:40.793Z
Have you seen my question: http://cstheory.stackexchange.com/q/972/873?
Sadeq Dousti
CC BY-SA 2.5
2010-10-26T17:43:35.260Z
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
Suresh Venkat
CC BY-SA 2.5
2010-10-26T17:49:32.630Z
no, but that was the exact thing I was hitting my head on the wall last night about which motivated this question!
gabgoh
CC BY-SA 2.5
2010-10-27T01:41:53.977Z
Also see this [question](http://cstheory.stackexchange.com/questions/2490/is-p-pp-p-p).
Kaveh
<complexity-classes><oracles>
Are Oracles Associative?
gabgoh
# Are Oracles Associative?

(Asked by: username_0 on 2010-10-26)

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?

**Tags:** complexity-classes, oracles

> **Comments:**
> **username_1**: Have you seen my question: http://cstheory.stackexchange.com/q/972/873?  
> **username_2**: 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  
> **username_0**: no, but that was the exact thing I was hitting my head on the wall last night about which motivated this question!  
> **username_3**: Also see this [question](http://cstheory.stackexchange.com/questions/2490/is-p-pp-p-p).  

---

## 2 answers

### Answer by username_4 on 2010-10-26. Score: 5

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

> **Comments:**
> **username_5**: Be careful: [P^NP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:D#delta2p) 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.  
> **username_4**: @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$.  

---

### Answer by username_1 on 2010-10-26. Score: 3

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 username_5). We will use the same convention used by [Ladner and Lynch](http://www.springerlink.com/content/j1562qn040167225/). The convention is well-described by [Bennett & Gill](http://dx.doi.org/10.1137/0210008):

> $\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](http://en.wikipedia.org/wiki/Oracle_machine#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}}$.

### Example

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}}$.

## Epilogue

A fruitful discussion with username_5 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.

> **Comments:**
> **username_5**: As I commented on [another question](http://cstheory.stackexchange.com/questions/2490/is-p-pp-p-p), “algorithm in class B with an oracle for a language L” does not have a universally accepted definition in general.  
> **username_1**: @Tsuyoshi: I edited the answer to represent which definition I'm using. Does it remove the ill-formed-ness?  
> **username_5**: No.  The added part only defines what LOGSPACE^A means, not what B^A means for something like B=NP^NP.  
> **username_1**: @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?  
> **username_5**: 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](http://dx.doi.org/10.1016/S0022-0000%2805%2980084-4).  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)  
> **username_5**: (cont’d)  Or course, it is possible to define (NP^NP)^A as NP^(NP^A), but if we define that way, the question “Is (NP^NP)^A equal to NP^(NP^A)?” becomes trivial.  

---

