<p>You should probably take a look at <a href="https://cstheory.stackexchange.com/questions/972/is-npnpnp-npnpnp">Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?</a> and <a href="https://cstheory.stackexchange.com/questions/2484/are-oracles-associative/2491#2491">Are Oracles Associative?</a>. I don't know any canonical definition of $(A^B)^C$ hence I've got the same problem as Tsuyoshi Ito.</p>

<p>If only the $P$ machine has access to oracle $O$, then yes, ${(P^O)}^O=P^O$ by definition.</p>

<p>If both the $P$ machine and the oracle $O$ can <em>both</em> query the oracle $O$, then just take $O=EXP$ as a counterexample: $(P^{EXP})^{EXP} = TIME(2^{2^{n^{O(1)}}})$ whereas $P^{EXP}=TIME(2^{n^{O(1)}})$.</p>

CC BY-SA 2.5
2010-10-27T03:54:36.163Z
@Arthur: $P^{NP}$ is not (known to be) equal to $NP \cup coNP$, nor is $P^{\Sigma_2 P}$ (known to be) equal to $\Sigma_2 P \cup \Pi_2 P$.  For example, $P^{NP}$ contains the entire Boolean hierarchy (over $NP$), of which $NP$ and $coNP$ are just the first levels.  $P^{\Sigma_k P}$ is also denoted $\Delta_{k} P$, and all that is known unconditionally is that $\Sigma_{k} P \cup \Pi_k P \subseteq \Delta_k P \subseteq \Sigma_{k+1} P \cap \Pi_{k+1} P$.
Joshua Grochow
CC BY-SA 2.5
2010-10-27T06:10:46.260Z
@Joshua: I remember $\Box_k P$ in place of a $\Delta_k P$ for denoting that (probably to keep it consistent with the notations in logic).
Kaveh
CC BY-SA 2.5
2010-10-27T13:39:18.653Z
@Kaveh: What kind of logic?  Computability theorists also use $\Delta_{k}^0$ for "computable with a $\Sigma_{k}^0$ oracle (now referring to levels of the arithmetic hierarchy).
Joshua Grochow
CC BY-SA 2.5
2010-10-27T15:48:25.260Z
@Joshua: In logic, $\Delta$ is use for formulas which are both $\Sigma$ and $\Pi$. I think $\Delta^0_k$ in computability theory is used in a [similar way](http://en.wikipedia.org/wiki/Arithmetical_hierarchy#The_arithmetical_hierarchy_of_sets_of_natural_numbers). For example $\Delta^0_1$ is exactly the decidable sets.
Kaveh
CC BY-SA 2.5
2010-10-27T16:52:11.197Z
@Kaveh: I forgot, you are correct about computability and logic. In computability theory, $REC^{\Sigma_k^0}$ happens to be equal to $\Sigma_{k+1}^0 \cap \Pi_{k+1}^0$. Is this situation the same in logic? However, in complexity I have seen  $\Delta_k P := P^{\Sigma_k P}$ in numerous places.  It's also that way in the zoo: http://qwiki.stanford.edu/index.php/Complexity_Zoo:P#ph.  Can you point me to a paper that uses the $\Box_k P$ notation (or even uses the Box_k notation in logic)?
Joshua Grochow
CC BY-SA 2.5
2010-10-27T19:38:52.457Z
@Joshua: No, I don't think they are equal. The box notation is very common in proof complexity, the oldest reference I know for it is Sam Buss's thesis from 1985. And yes, you are right, the use of $\Delta$ is also common in complexity theory. :)
Kaveh
CC BY-SA 2.5
2010-10-28T15:45:04.107Z
@Joshua Thank you for the correction, I don't know why I thought that there was an equality. I did edit since it was false, sorry if your comment won't make sens anymore. Anyway, the second part of the comment is still valid (I hope)
Arthur MILCHIOR
CC BY-SA 3.0
2010-10-26T23:00:24.270Z
2014-06-23T19:48:35.937Z
2017-04-13T12:32:28.743Z
Arthur MILCHIOR
<p>Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one.</p>

<p>More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?</p>

CC BY-SA 2.5
2010-10-26T22:34:29.550Z
What is the definition of (P^#P)^#P?
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-26T22:41:46.077Z
We know that $P^{\#P}$ is a polynomial time Turing machine with a $\#P$ oracle. $(P^{\#P})^{\#P}$ means a $P^{\#P}$ Turing machine with a $\#P$ oracle.
Mike Chen
CC BY-SA 2.5
2010-10-26T22:53:04.387Z
I was asking the definition of what you call a “P^#P Turing machine with a #P oracle.”  I do not know a universal definition of how to attach an oracle to an oracle Turing machine.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-26T22:55:53.303Z
@Mike Chen: I think the question is whether you mean the machine has simply two oracle tapes, or something else (i.e. the oracle has an oracle)? Because the answer is different in each case.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-27T01:30:31.223Z
Let me repeat what Tsuyoshi and Joe have said in an other way. The class $A^B$ is not well-defined, i.e. we don't have a definition for what oracle access for a language means, we have definition**s** for oracle access for machines, and even for machines there is not a universal definition. With one definition there is an oracle $A$ s.t. $L^A=PSpace^A$, with another one we can prove that for every oracle $A$, $L^A\neq PSpace^A$. You have to be specific and give more details about the oracle mechanism to make your question well-defined.
Kaveh
CC BY-SA 2.5
2010-11-17T22:30:09.380Z
@Joe: Well, I mean the machine has simply two oracle tapes. Sorry for the confusion.
Mike Chen
<cc.complexity-theory><complexity-classes><oracles><counting-complexity>
Is $P^{\#P}=(P^{\#P})^{\#P}$ ?
Mike Chen
# Is $P^{\#P}=(P^{\#P})^{\#P}$ ?

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

Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one.

More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?

**Tags:** cc.complexity-theory, complexity-classes, oracles, counting-complexity

> **Comments:**
> **username_1**: What is the definition of (P^#P)^#P?  
> **username_0**: We know that $P^{\#P}$ is a polynomial time Turing machine with a $\#P$ oracle. $(P^{\#P})^{\#P}$ means a $P^{\#P}$ Turing machine with a $\#P$ oracle.  
> **username_1**: I was asking the definition of what you call a “P^#P Turing machine with a #P oracle.”  I do not know a universal definition of how to attach an oracle to an oracle Turing machine.  
> **username_2**: @username_0: I think the question is whether you mean the machine has simply two oracle tapes, or something else (i.e. the oracle has an oracle)? Because the answer is different in each case.  
> **username_3**: Let me repeat what Tsuyoshi and Joe have said in an other way. The class $A^B$ is not well-defined, i.e. we don't have a definition for what oracle access for a language means, we have definition**s** for oracle access for machines, and even for machines there is not a universal definition. With one definition there is an oracle $A$ s.t. $L^A=PSpace^A$, with another one we can prove that for every oracle $A$, $L^A\neq PSpace^A$. You have to be specific and give more details about the oracle mechanism to make your question well-defined.  
> **username_0**: @Joe: Well, I mean the machine has simply two oracle tapes. Sorry for the confusion.  

---

## 1 answers

### Answer by username_4 on 2010-10-26. Score: 13 | Accepted answer

You should probably take a look at [Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?](https://cstheory.stackexchange.com/questions/972/is-npnpnp-npnpnp) and [Are Oracles Associative?](https://cstheory.stackexchange.com/questions/2484/are-oracles-associative/2491#2491). I don't know any canonical definition of $(A^B)^C$ hence I've got the same problem as username_1.

If only the $P$ machine has access to oracle $O$, then yes, ${(P^O)}^O=P^O$ by definition.

If both the $P$ machine and the oracle $O$ can *both* query the oracle $O$, then just take $O=EXP$ as a counterexample: $(P^{EXP})^{EXP} = TIME(2^{2^{n^{O(1)}}})$ whereas $P^{EXP}=TIME(2^{n^{O(1)}})$.

> **Comments:**
> **username_5**: @Arthur: $P^{NP}$ is not (known to be) equal to $NP \cup coNP$, nor is $P^{\Sigma_2 P}$ (known to be) equal to $\Sigma_2 P \cup \Pi_2 P$.  For example, $P^{NP}$ contains the entire Boolean hierarchy (over $NP$), of which $NP$ and $coNP$ are just the first levels.  $P^{\Sigma_k P}$ is also denoted $\Delta_{k} P$, and all that is known unconditionally is that $\Sigma_{k} P \cup \Pi_k P \subseteq \Delta_k P \subseteq \Sigma_{k+1} P \cap \Pi_{k+1} P$.  
> **username_3**: @Joshua: I remember $\Box_k P$ in place of a $\Delta_k P$ for denoting that (probably to keep it consistent with the notations in logic).  
> **username_5**: @username_3: What kind of logic?  Computability theorists also use $\Delta_{k}^0$ for "computable with a $\Sigma_{k}^0$ oracle (now referring to levels of the arithmetic hierarchy).  
> **username_3**: @Joshua: In logic, $\Delta$ is use for formulas which are both $\Sigma$ and $\Pi$. I think $\Delta^0_k$ in computability theory is used in a [similar way](http://en.wikipedia.org/wiki/Arithmetical_hierarchy#The_arithmetical_hierarchy_of_sets_of_natural_numbers). For example $\Delta^0_1$ is exactly the decidable sets.  
> **username_5**: @username_3: I forgot, you are correct about computability and logic. In computability theory, $REC^{\Sigma_k^0}$ happens to be equal to $\Sigma_{k+1}^0 \cap \Pi_{k+1}^0$. Is this situation the same in logic? However, in complexity I have seen  $\Delta_k P := P^{\Sigma_k P}$ in numerous places.  It's also that way in the zoo: http://qwiki.stanford.edu/index.php/Complexity_Zoo:P#ph.  Can you point me to a paper that uses the $\Box_k P$ notation (or even uses the Box_k notation in logic)?  
> **username_3**: @Joshua: No, I don't think they are equal. The box notation is very common in proof complexity, the oldest reference I know for it is Sam Buss's thesis from 1985. And yes, you are right, the use of $\Delta$ is also common in complexity theory. :)  
> **username_4**: @Joshua Thank you for the correction, I don't know why I thought that there was an equality. I did edit since it was false, sorry if your comment won't make sens anymore. Anyway, the second part of the comment is still valid (I hope)  

---

