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 ...
- 18.6k
7
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 ⊆ ...
- 1,616
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 $...
- 13.3k
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)}$.
...
- 18.6k
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 ...
- 2,204
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 ...
- 18.6k
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 ...
- 38.5k
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 ...
- 1,294
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible