# Are Oracles Associative?

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?

-
– Sadeq Dousti Oct 26 '10 at 17:30

1
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♦ Oct 26 '10 at 17:43
no, but that was the exact thing I was hitting my head on the wall last night about which motivated this question! – gabgoh Oct 26 '10 at 17:49
– Kaveh♦ Oct 27 '10 at 1:41

## 2 Answers

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

-

3
– Tsuyoshi Ito Oct 26 '10 at 23:00
@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 Oct 28 '10 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}}$.

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

-

3
– Tsuyoshi Ito Oct 27 '10 at 0:11
@Tsuyoshi: I edited the answer to represent which definition I'm using. Does it remove the ill-formed-ness? – Sadeq Dousti Oct 27 '10 at 5:24
No. The added part only defines what LOGSPACE^A means, not what B^A means for something like B=NP^NP. – Tsuyoshi Ito Oct 27 '10 at 5:31
@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 Oct 27 '10 at 5:37

3
– Tsuyoshi Ito Oct 27 '10 at 5:57
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 57, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9404066801071167, "perplexity_flag": "middle"}