1

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Mike Chen
  • 709
  • 4
  • 10
  • 3
    What is the definition of (P^#P)^#P? – Tsuyoshi Ito Oct 26 '10 at 22:34
  • 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 Oct 26 '10 at 22:41
  • 5
    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 Oct 26 '10 at 22:53
  • 6
    @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 Oct 26 '10 at 22:55
  • 5
    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. – Kaveh Oct 27 '10 at 01:30
  • @Joe: Well, I mean the machine has simply two oracle tapes. Sorry for the confusion. – Mike Chen Nov 17 '10 at 22:30

1 Answers1

13

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

Community
  • 1
Arthur MILCHIOR
  • 1,561
  • 10
  • 19
  • 1
    @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 Oct 27 '10 at 03:54
  • @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 Oct 27 '10 at 06:10
  • @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 Oct 27 '10 at 13:39
  • @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. For example $\Delta^0_1$ is exactly the decidable sets. – Kaveh Oct 27 '10 at 15:48
  • 1
    @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 Oct 27 '10 at 16:52
  • 1
    @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 Oct 27 '10 at 19:38
  • @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 Oct 28 '10 at 15:45