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

  • 3
    $\begingroup$ What is the definition of (P^#P)^#P? $\endgroup$ Oct 26, 2010 at 22:34
  • $\begingroup$ 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. $\endgroup$
    – Mike Chen
    Oct 26, 2010 at 22:41
  • 5
    $\begingroup$ 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. $\endgroup$ Oct 26, 2010 at 22:53
  • 6
    $\begingroup$ @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. $\endgroup$ Oct 26, 2010 at 22:55
  • 5
    $\begingroup$ 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 definitions 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. $\endgroup$
    – Kaveh
    Oct 27, 2010 at 1:30

1 Answer 1


You should probably take a look at Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$? and Are Oracles Associative?. I don't know any canonical definition of $(A^B)^C$ hence I've got the same problem as Tsuyoshi Ito.

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

  • 1
    $\begingroup$ @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$. $\endgroup$ Oct 27, 2010 at 3:54
  • $\begingroup$ @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). $\endgroup$
    – Kaveh
    Oct 27, 2010 at 6:10
  • $\begingroup$ @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). $\endgroup$ Oct 27, 2010 at 13:39
  • 1
    $\begingroup$ @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: 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)? $\endgroup$ Oct 27, 2010 at 16:52
  • 1
    $\begingroup$ @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. :) $\endgroup$
    – Kaveh
    Oct 27, 2010 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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