New answers tagged

1 vote

Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets

I think the problem of hyperedge coloring of a 3-regular 3-uniform hypergraph (with 3 colors) is reducible to this problem and vice versa, where the set X is corresponds to the vertex set V and each ...
user avatar
10 votes

Lower-bounds under SETH

Most problems need at least linear time, so $O(n \log n)$ may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by ...
user avatar
1 vote
Accepted

Showing that a modification of an NP-Complete problem is also NP-Complete

tl;dr: Showing that the Extended Knapsack problem is NP-Complete is easy through the original Knapsack, but you have to define the two problems correctly. For a problem to be NP-Complete, it has to be ...
user avatar
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)}$. ...
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 ...
user avatar

Top 50 recent answers are included