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 ...
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)}$.
...
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 ...
Top 50 recent answers are included
Related Tags
cc.complexity-theory × 2878complexity-classes × 462
reference-request × 338
np-hardness × 326
ds.algorithms × 242
graph-theory × 233
circuit-complexity × 229
sat × 142
counting-complexity × 137
time-complexity × 136
graph-algorithms × 135
quantum-computing × 113
lower-bounds × 111
reductions × 90
big-picture × 80
approximation-algorithms × 77
approximation-hardness × 76
lo.logic × 75
co.combinatorics × 74
np × 72
boolean-functions × 70
computability × 63
cr.crypto-security × 58
optimization × 56
np-complete × 56