The nexp tag has no wiki summary.
7
votes
1answer
474 views
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
4
votes
1answer
255 views
NEXP Cook-Levin
I've come across the following lemma (without proof):
The first part of the lemma states that for any $x$, there's a 3CNF exponential Boolean formula $f(x)$ that is satisfiable if and only if $x \in ...
2
votes
0answers
478 views
Proving MIP=NEXP using the PCP theorem
I need to write a proof that the class of languages with multi-prover interactive proof systems (MIP) is equivalent to NEXP. I am supposed to somehow use the PCP theorem (NP=PCP(log(n),1)) to prove ...
7
votes
3answers
443 views
Complexity Class NEXP$^\text{NP}$
I have a problem which is in NEXP$^{\text{NP}}$ and can also be solved by an alternating TM using exponential time and just one alternation (starting in an existential state).
Is there anything known ...
16
votes
5answers
1k views
NEXP-complete problems
There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...
