6
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\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$ – Tsuyoshi Ito Jun 24 '12 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$ – Kristoffer Arnsfelt Hansen Jun 24 '12 at 17:09
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks, this is what I thought but wanted to make sure I was understanding the oracle definitions properly. $\endgroup$ – Joel Jun 22 '12 at 9:34
-2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 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$ – Tsuyoshi Ito Jun 24 '12 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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