Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Have you seen my question: cstheory.stackexchange.com/q/972/873? –  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
    
Also see this question. –  Kaveh Oct 27 '10 at 1:41
add comment

2 Answers 2

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.

share|improve this answer
3  
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. –  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  
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) –  Tsuyoshi Ito Oct 27 '10 at 5:57
show 1 more comment

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

share|improve this answer
4  
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. –  Tsuyoshi Ito Oct 26 '10 at 23:00
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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