<ol>
<li><p>Complexity Zoo tells me that, as proved in Li’s PhD thesis, APP is low for PP, thus
$$\mathrm{P^{AWPP}\subseteq P^{APP}\subseteq PP^{APP}=PP.}$$
So, if PH were included in one of these classes, it would not only make $\mathrm{PH\subseteq PP}$ more plausible, it would outright imply it.</p></li>
<li><p>I don’t understand the question. AWPP and APP <em>already are</em> classes of decision problems, so it does not make sense to ask what would be their decision analogue.</p></li>
</ol>

CC BY-SA 3.0
2016-05-02T15:35:41.143Z
I was asking something like $PP$ contains problems like if perm(M)>k. So what does AWPP and APP contain?
Turbo
CC BY-SA 3.0
2016-05-02T15:47:26.443Z
Since APP is low for PP then AWPP should also be low for PP while PP^PP goes on to define counting hierarchy. Would NP^AWPP or NP^APP live below or above P^PP and if they live below would it contain PH as well? Seems like NP^NP should be in NP^AWPP and hence NP^NP^NP and so on.
Turbo
CC BY-SA 3.0
2016-05-02T16:05:19.793Z
$\mathrm{NP^{AWPP}\subseteq NP^{APP}\subseteq PP^{APP}=PP}$. This does not imply anything about $\mathrm{NP^{NP}}$ (or higher levels of the hierarchy), as I see no reason for NP to be included in APP.
Emil Jeřábek
CC BY-SA 3.0
2016-05-02T16:17:12.600Z
NP is in AWPP https://www.cs.indiana.edu/~lvoufo/qcc.pdf. So is  NP^NP^NP and so on in NP^AWPP or NP^APP?
Turbo
CC BY-SA 3.0
2016-05-02T16:24:17.743Z
And you are inferring that from an unreferenced passing remark in some *slides*? It’s wrong. See http://eccc.hpi-web.de/report/2002/036/ for what is actually known about these classes. In particular, there is an oracle $G$ such that $\mathrm{AWPP}^G=\mathrm P^G$, but $\mathrm{PH}^G$ does not collapse, so $\mathrm{NP}^G\nsubseteq \mathrm{AWPP}^G$.
Emil Jeřábek
CC BY-SA 3.0
2016-05-02T16:30:47.803Z
Oh I see Interesting. I think other way to see would be since NP is PP there for NP in AWPP would mean NP^NP is in PP^AWPP but since AWPP is low for PP we would have NP^NP would be in PP and extrapolating we would have PH in PP which is unknown. So NP in AWPP is possible but not known.
Turbo
CC BY-SA 3.0
2016-05-02T16:36:32.883Z
would you also know analogies? 
like PP contains problems like if perm(M)>k so what does AWPP and APP contain?
Turbo
CC BY-SA 3.0
2016-05-02T14:33:51.360Z
2016-05-02T14:33:51.360Z
Emil Jeřábek
<p>We know that $PH$ is in $P^{PP}$ or in $P^{\#P}$ and we do not know if $PH$ is in $PP$. We know $AWPP$ and $APP$ are weakening of $PP$ where $AWPP$ is in $APP$ is in $PP$.</p>

<p><strong>(1)</strong> Is it possible if $PH$ is in $P^{AWPP}$ or $P^{APP}$ or is there any consequences if $PH$ is in $P^{AWPP}$ or $P^{APP}$? Would it make it more plausible $PH$ is in $PP$?</p>

<p><strong>(2)</strong> Is there an analog of decision version of $\#P$ which is $PP$ for clases $AWPP$ or $APP$?</p>

<cc.complexity-theory>
Evidence of containment of $PH$
Turbo
# Evidence of containment of $PH$

(Asked by: username_0 on 2016-05-02)

We know that $PH$ is in $P^{PP}$ or in $P^{\#P}$ and we do not know if $PH$ is in $PP$. We know $AWPP$ and $APP$ are weakening of $PP$ where $AWPP$ is in $APP$ is in $PP$.

**(1)** Is it possible if $PH$ is in $P^{AWPP}$ or $P^{APP}$ or is there any consequences if $PH$ is in $P^{AWPP}$ or $P^{APP}$? Would it make it more plausible $PH$ is in $PP$?

**(2)** Is there an analog of decision version of $\#P$ which is $PP$ for clases $AWPP$ or $APP$?

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2016-05-02. Score: 5 | Accepted answer

1. Complexity Zoo tells me that, as proved in Li’s PhD thesis, APP is low for PP, thus
   $$\mathrm{P^{AWPP}\subseteq P^{APP}\subseteq PP^{APP}=PP.}$$
   So, if PH were included in one of these classes, it would not only make $\mathrm{PH\subseteq PP}$ more plausible, it would outright imply it.
2. I don’t understand the question. AWPP and APP *already are* classes of decision problems, so it does not make sense to ask what would be their decision analogue.

> **Comments:**
> **username_0**: I was asking something like $PP$ contains problems like if perm(M)>k. So what does AWPP and APP contain?  
> **username_0**: Since APP is low for PP then AWPP should also be low for PP while PP^PP goes on to define counting hierarchy. Would NP^AWPP or NP^APP live below or above P^PP and if they live below would it contain PH as well? Seems like NP^NP should be in NP^AWPP and hence NP^NP^NP and so on.  
> **username_1**: $\mathrm{NP^{AWPP}\subseteq NP^{APP}\subseteq PP^{APP}=PP}$. This does not imply anything about $\mathrm{NP^{NP}}$ (or higher levels of the hierarchy), as I see no reason for NP to be included in APP.  
> **username_0**: NP is in AWPP https://www.cs.indiana.edu/~lvoufo/qcc.pdf. So is  NP^NP^NP and so on in NP^AWPP or NP^APP?  
> **username_1**: And you are inferring that from an unreferenced passing remark in some *slides*? It’s wrong. See http://eccc.hpi-web.de/report/2002/036/ for what is actually known about these classes. In particular, there is an oracle $G$ such that $\mathrm{AWPP}^G=\mathrm P^G$, but $\mathrm{PH}^G$ does not collapse, so $\mathrm{NP}^G\nsubseteq \mathrm{AWPP}^G$.  
> **username_0**: Oh I see Interesting. I think other way to see would be since NP is PP there for NP in AWPP would mean NP^NP is in PP^AWPP but since AWPP is low for PP we would have NP^NP would be in PP and extrapolating we would have PH in PP which is unknown. So NP in AWPP is possible but not known.  
> **username_0**: would you also know analogies?  like PP contains problems like if perm(M)>k so what does AWPP and APP contain?  

---

