# Tag Info

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 ...

### 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 ...
• 26.3k
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 ...
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)}$. ...
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 ...