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 ...
- 776
Top 50 recent answers are included