<p>It is clear that <span class="math-container">$NEXP\subseteq EXP^{NP}$</span>, as a TM with exponential run time can simply query the NP oracle with an exponentially long query. However, it's not clear that the reverse <span class="math-container">$EXP^{NP}\subseteq NEXP$</span> is true.
Are there any complexity theoretic conjectures which suggest this is not true and hence <span class="math-container">$EXP^{NP}\not=NEXP$</span>?</p>

CC BY-SA 4.0
2020-03-06T13:32:34.180Z
Isn't it the other way around?
M.Monet
CC BY-SA 4.0
2020-03-06T16:54:51.770Z
I don’t really understand what do you expect to get. $\mathrm{EXP^{NP}\ne NEXP}$ is itself a complexity theoretic conjecture. This is implied, for example, by $\mathrm{NEXP\ne coNEXP}$.
Emil Jeřábek
CC BY-SA 4.0
2020-03-06T16:57:41.613Z
@M.Monet Isn’t what the other way round? But if you mean the inclusions, they are stated correctly in the question: $\mathrm{NEXP\subseteq EXP^{NP}}$ is true, while  $\mathrm{EXP^{NP}\subseteq NEXP}$ is likely false.
Emil Jeřábek
CC BY-SA 4.0
2020-03-06T17:39:50.670Z
Oh yes sorry I read too fast. Should I delete the comments?
M.Monet
CC BY-SA 4.0
2020-03-06T21:02:30.453Z
@user138901 - See my similar question here: https://cstheory.stackexchange.com/questions/41500/indications-that-strengthen-the-conjecture-nexp-%e2%8a%8a-expnp     There are many evidence that strengthen this conjecture, and I am still looking for more...
Avi Tal
CC BY-SA 4.0
2020-03-07T18:08:45.167Z
Thanks Avi, I must have missed this. I'll close this question given that it seems to be the same as yours.
Hans Schmuber
<cc.complexity-theory><complexity-classes><time-complexity>
Are there complexity theory consequences of the collapse NEXP=EXP^NP?
Hans Schmuber
# Are there complexity theory consequences of the collapse NEXP=EXP^NP?

(Asked by: username_0 on 2020-03-06)

It is clear that $NEXP\subseteq EXP^{NP}$, as a TM with exponential run time can simply query the NP oracle with an exponentially long query. However, it's not clear that the reverse $EXP^{NP}\subseteq NEXP$ is true.
Are there any complexity theoretic conjectures which suggest this is not true and hence $EXP^{NP}\not=NEXP$?

**Tags:** cc.complexity-theory, complexity-classes, time-complexity

> **Comments:**
> **username_1**: Isn't it the other way around?  
> **username_2**: I don’t really understand what do you expect to get. $\mathrm{EXP^{NP}\ne NEXP}$ is itself a complexity theoretic conjecture. This is implied, for example, by $\mathrm{NEXP\ne coNEXP}$.  
> **username_2**: @username_1 Isn’t what the other way round? But if you mean the inclusions, they are stated correctly in the question: $\mathrm{NEXP\subseteq EXP^{NP}}$ is true, while  $\mathrm{EXP^{NP}\subseteq NEXP}$ is likely false.  
> **username_1**: Oh yes sorry I read too fast. Should I delete the comments?  
> **username_3**: @user138901 - See my similar question here: https://cstheory.stackexchange.com/questions/41500/indications-that-strengthen-the-conjecture-nexp-%e2%8a%8a-expnp     There are many evidence that strengthen this conjecture, and I am still looking for more...  
> **username_0**: Thanks Avi, I must have missed this. I'll close this question given that it seems to be the same as yours.  

---

## 0 answers

