<p>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.</p>

CC BY-SA 3.0
2012-06-22T09:34:23.057Z
Thanks, this is what I thought but wanted to make sure I was understanding the oracle definitions properly.
Joel
CC BY-SA 3.0
2012-06-21T11:05:06.320Z
2012-06-21T11:05:06.320Z
Kristoffer Arnsfelt Hansen
<p>Let's take this step by step, so we are not confused by that small tower of oracles.</p>

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

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

<p>So yes, the problem is in $NP^{P^{PP^{PP^{PP}}}}$.</p>

CC BY-SA 3.0
2012-06-24T00:46:12.860Z
“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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-21T09:07:56.567Z
2012-06-21T09:07:56.567Z
chazisop
<p>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}}}}$.</p>

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

CC BY-SA 3.0
2012-06-24T00:50:42.357Z
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.”
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-24T17:09:37.897Z
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.
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><counting-complexity><oracles><computing-over-reals>
Oracle complexity of a problem in the Counting Hierarchy
Joel
# Oracle complexity of a problem in the Counting Hierarchy

(Asked by: username_0 on 2012-06-20)

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

**Tags:** cc.complexity-theory, counting-complexity, oracles, computing-over-reals
> **Comments:**
> **username_1**: 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.”  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_2 on 2012-06-21. Score: 5

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.

> **Comments:**
> **username_0**: Thanks, this is what I thought but wanted to make sure I was understanding the oracle definitions properly.  

---

### Answer by username_3 on 2012-06-21. Score: -2

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

> **Comments:**
> **username_1**: “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.  

---

