<p>I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP.</p>

<p>Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper.</p>

<p>Some Examples:
1.  A paper by Shuichi Hirahara: “Identifying an honest EXP^NP oracle among many”, which states that “No instance checker for EXP^NP -complete languages exists unless EXP^NP = NEXP” <a href="https://arxiv.org/abs/1502.07258" rel="noreferrer">https://arxiv.org/abs/1502.07258</a></p>

<ol start="2">
<li>A paper by Laszlo Babai, Lance Fortnow and Carsten Lund: “NON-DETERMINISTIC EXPONENTIAL TIME HAS TWO-PROVER INTERACTIVE PROTOCOLS” which states that we do not know whether NEXP provers are sufficient to prove any NEXP language to a verifier, but the best upper bound we know on the power of the provers for NEXP is EXP^NP
<a href="http://people.cs.uchicago.edu/~fortnow/papers/mip2.pdf" rel="noreferrer">http://people.cs.uchicago.edu/~fortnow/papers/mip2.pdf</a></li>
</ol>

<p>Are there any additional known results on the conjecture of NEXP ⊊ EXP^NP?
What are its implications on the separation of other classes?</p>

<p>Thanks</p>

<complexity-classes><oracles><nexp>
Indications that strengthen the conjecture: NEXP ⊊ EXP^NP
Avi Tal
# Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

(Asked by: username_0 on 2018-09-06)

I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP.

Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper.

Some Examples:
1. A paper by Shuichi Hirahara: “Identifying an honest EXP^NP oracle among many”, which states that “No instance checker for EXP^NP -complete languages exists unless EXP^NP = NEXP” <https://arxiv.org/abs/1502.07258>

2. A paper by Laszlo Babai, Lance Fortnow and Carsten Lund: “NON-DETERMINISTIC EXPONENTIAL TIME HAS TWO-PROVER INTERACTIVE PROTOCOLS” which states that we do not know whether NEXP provers are sufficient to prove any NEXP language to a verifier, but the best upper bound we know on the power of the provers for NEXP is EXP^NP
   <http://people.cs.uchicago.edu/~fortnow/papers/mip2.pdf>

Are there any additional known results on the conjecture of NEXP ⊊ EXP^NP?
What are its implications on the separation of other classes?

Thanks

**Tags:** complexity-classes, oracles, nexp


---

## 0 answers

