New answers tagged np-complete
-2
votes
Does Memcomputing really solve an NP-complete problem?
Just to add/update to the answer here. Scott Aaronson's critique is basically a rehashed critique of analog computers. MemComputers are not necessarily analog, the authors mention this in their 2015 ...
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 ...
1
vote
Is "choosability of subsets" NP-hard?
Yes, and one can give a reduction from one-in-three 3SAT, which is the following problem: given a conjunctive normal form with three literals per clause, the problem is to determine whether there ...
Top 50 recent answers are included
Related Tags
np-complete × 151cc.complexity-theory × 56
np-hardness × 39
graph-theory × 18
np × 17
graph-algorithms × 13
reductions × 13
reference-request × 12
complexity-classes × 11
subset-sum × 9
sat × 7
time-complexity × 6
polynomial-time × 6
ds.algorithms × 4
approximation-algorithms × 4
p-vs-np × 4
complexity × 4
factoring × 4
big-picture × 3
planar-graphs × 3
nt.number-theory × 3
polynomials × 3
integer-programming × 3
set-cover × 3
partition-problem × 3