8 votes
Accepted

NEXPTIME-completeness with more time for reductions

The trouble with exponential-time reductions is that they may exponentially expand the input, and this leads to all sorts of weirdness. So, to begin with, neither EXP nor NEXP is closed under exp-time ...
Emil Jeřábek's user avatar
6 votes

Why should we believe that $NEXP \not \subset P/poly$

Proving this separation seems very hard since we don't even know how to separate EXP^NP (which contains NEXP) from P/Poly, and we know that this separation does not algebrize. In addition, if EXP^NP ⊆ ...
Avi Tal's user avatar
  • 1,606
6 votes
Accepted

Why should we believe that $NEXP \not \subset P/poly$

The best evidence is in my opinion follows due to the results of Ryan Williams on even a mild speed up of $CIRCUITSAT$ provides $NQP\not\subset P/poly$ which is an extremely strong result compared to $...
Turbo's user avatar
  • 12.9k
6 votes
Accepted

Best known algorithm for NEXP-complete problem

For every $\epsilon>0$, there exists an NEXP-complete language $L_\epsilon$ in $\mathrm{NTIME}(2^{n^\epsilon})$, and therefore in $\mathrm{DTIME}(2^{2^{n^\epsilon}})$, which is below $2^{o(2^n)}$. ...
Emil Jeřábek's user avatar
6 votes

Results comparing BQP and NEXP

The oracle you ask for has $P=NP\ne BQP=NEXP$, and therefore it has $BQP\ne PH$. Finding any oracle relative to which $BQP\ne PH$ was an open problem for twenty years until Raz and Tal [1] found such ...
Lieuwe Vinkhuijzen's user avatar
4 votes
Accepted

Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

This is quite unlikely to hold, because $\mathrm{EXP_{poly}^{NEXP}}$ actually coincides with $\Theta^{\exp}_2$, the exponential analogue of the class $\Theta^P_2$, which is presumably a strict ...
Emil Jeřábek's user avatar
4 votes
Accepted

On succinct $EXP$ and $NEXP$ complete problems?

The description of a succinct problem has very little to do with graphs, per se. Given a language $L \subseteq \Sigma^*$, we can define its succinct version as the set of Boolean circuits $C$ such ...
Joshua Grochow's user avatar
3 votes

Best known algorithm for NEXP-complete problem

In a quite recent paper https://arxiv.org/abs/2104.10621 the authors present an algorithm running in time $\delta^{2^n}$, where $\delta = 1.4423$, for the following NExpTime-complete problem: given a ...
Reijo Jaakkola's user avatar
1 vote

CNF encoding of set cover - NExpTime-completness

As I suspected in my question, they are useful results in the literature that can be exploited to characterize the complexity of the problem. There is a reduction from the dominant set problem for ...
Jean-Francois Raskin's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible