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

  • $\begingroup$ 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.” $\endgroup$ Jun 24, 2012 at 0:50
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 24, 2012 at 17:09

2 Answers 2


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.

  • $\begingroup$ Thanks, this is what I thought but wanted to make sure I was understanding the oracle definitions properly. $\endgroup$
    – Joel
    Jun 22, 2012 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}}}}$.

  • 5
    $\begingroup$ “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. $\endgroup$ Jun 24, 2012 at 0:46

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.