12

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?

gabgoh
  • 1,548
  • 12
  • 22

2 Answers2

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

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
Arthur MILCHIOR
  • 1,561
  • 10
  • 19
  • 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
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 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.

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
  • 4
    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 00: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 05: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 05: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 05:37
  • 4
    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 05:57
  • (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 Oct 27 '10 at 06:03