<p><strong>(1)</strong> $PP$ contains problems like 'is perm(M)>k'. So what problems does $AWPP$ and $APP$ contain with respect to permanent? </p>

<p><strong>(2)</strong> Since it is not known if $NP$ is in $AWPP$ or $APP$ is there a candidate problem in $NP$ not in $AWPP$ and outside $NP$ complete problems? Or does $NP\cap AWPP = NP\backslash NPC$?</p>

CC BY-SA 3.0
2016-05-02T17:56:57.080Z
Now, (2) is also non sequitur.
Emil Jeřábek
CC BY-SA 3.0
2016-05-02T18:16:06.530Z
@EmilJeřábek I am assuming no class contains $NP\backslash NPI\cup P$. Is this still not logical?
Turbo
CC BY-SA 3.0
2016-05-02T21:02:50.280Z
Do you mean $(NP\setminus NPI)\cup P$ or $NP\setminus(NPI\cup P)$? Either way, there are certainly classes that contain it, so why would you assume otherwise? How is any of this related to the problem whether it is possible for $\mathit{NP\cap AWPP}$ to equal $\mathit{NP\setminus NPC}$ (that is, $\mathit{NPI\cup P}$)?
Emil Jeřábek
CC BY-SA 3.0
2016-05-02T21:14:06.450Z
@EmilJeřábek I corrected post I am just looking for a problem outside P and inside NP which is outside AWPP. This should be possible.
Turbo
CC BY-SA 3.0
2016-05-02T21:14:40.483Z
http://chat.stackexchange.com/rooms/39199/discussion-between-emil-jerabek-and-turbo
Turbo
<cc.complexity-theory>
On classes $AWPP$ and $APP$
Turbo
# On classes $AWPP$ and $APP$

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

**(1)** $PP$ contains problems like 'is perm(M)>k'. So what problems does $AWPP$ and $APP$ contain with respect to permanent?

**(2)** Since it is not known if $NP$ is in $AWPP$ or $APP$ is there a candidate problem in $NP$ not in $AWPP$ and outside $NP$ complete problems? Or does $NP\cap AWPP = NP\backslash NPC$?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Now, (2) is also non sequitur.  
> **username_0**: @EmilJeřábek I am assuming no class contains $NP\backslash NPI\cup P$. Is this still not logical?  
> **username_1**: Do you mean $(NP\setminus NPI)\cup P$ or $NP\setminus(NPI\cup P)$? Either way, there are certainly classes that contain it, so why would you assume otherwise? How is any of this related to the problem whether it is possible for $\mathit{NP\cap AWPP}$ to equal $\mathit{NP\setminus NPC}$ (that is, $\mathit{NPI\cup P}$)?  
> **username_0**: @EmilJeřábek I corrected post I am just looking for a problem outside P and inside NP which is outside AWPP. This should be possible.  
> **username_0**: http://chat.stackexchange.com/rooms/39199/discussion-between-emil-jerabek-and-turbo  

---

## 0 answers

