# Oracle complexity of a problem in the Counting Hierarchy

In "On The Complexity of Numerical Analysis" (SIAM J. Comp. Vol. 38, 2009), Allender et al. introduce the problem of PosSLP and show that its complexity lies in the counting hierarchy, and more precisely in $P^{\mathit{PP}^{\mathit{PP}^{\mathit{PP}}}}$.

I have a problem, call it $X$, that I have shown can be solved in $\mathit{NP}^{\mathit{PosSLP}}$. Can I correctly conclude that $X$ lies in $\mathit{NP}^{\mathit{PP}^{\mathit{PP}^{\mathit{PP}}}}$?

• I wonder why would anyone upvote this question. It is a typical example of a bad question: you do not state what you understand and what you do not. Because of this, people cannot post any meaningful answer. Kristoffer Arnsfelt Hansen’s answer just repeats what you wrote in the question with one additional word “Yes.” Jun 24 '12 at 0:50
• Just for the record: I decided to answer this basic question, since I saw a very misleading answer was given and it was even voted up. Jun 24 '12 at 17:09

Yes. Each time your $\sf NP$ machine want to query the $\sf PosSLP$ oracle, simply simulate the polynomial time oracle Turing machine underlying the inclusion $\sf PosSLP \subseteq {P}^{{PP}^{PP^{PP}}}$, passing its oracle queries to the $\sf {PP}^{PP^{PP}}$ oracle.

• Thanks, this is what I thought but wanted to make sure I was understanding the oracle definitions properly.
– Joel
Jun 22 '12 at 9:34

Let's take this step by step, so we are not confused by that small tower of oracles.

$X \in NP^{PosSLP}$. Since $PosSLP \in P^{PP^{PP^{PP}}}$, we derive that $X \in NP^{P^{PP^{PP^{PP}}}}$. We want to prove that $X \in NP^{PP^{PP^{PP}}}$.

Since $NP \subseteq NP^{P}$ and due to oracle properties, adding the power of the same oracles to both hands of the relation preserves it. Therefore we have: $NP^{PP^{PP^{PP}}} \subseteq NP^{P^{PP^{PP^{PP}}}}$.

So yes, the problem is in $NP^{P^{PP^{PP^{PP}}}}$.

• “adding the power of the same oracles to both hands of the relation preserves it.” This reasoning is incorrect. If it were true, we would already know P≠NP because there is a language A such that P^A≠NP^A (the Baker-Gill-Solovay theorem). But a famous counterexample in complexity theory is that IP=PSPACE but IP^A≠PSPACE^A for some language A. Jun 24 '12 at 0:46