New answers tagged

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

Top 50 recent answers are included