New answers tagged cc.complexity-theory
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 ...
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 ...
- 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 ...
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)}$.
...
- 14.8k
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 ...
- 776
Top 50 recent answers are included