News for hackers. Stuff that matters.
Re:Breaking np-complete with memcomputing. Is it real? by cousin_it on Thursday July 09, 2015 @09:45AM (#9857797)
There's no such thing as a "useful subset" of NP-complete problems. If you solve one of them, you've automatically solved all of them, because they are all reducible to each other.
Re:Breaking np-complete with memcomputing. Is it real? by ikeboy on Thursday July 09, 2015 @12:31PM (#9858929)
There could turn out to be a tractable algorithm for some NP-complete problems, but when you do the reduction, it expands and is no longer tractable. There are also other ways in which different NP-complete problems are meaningfully different. See https://cstheory.stackexchange.com/questions/24879/easier-an... for some discussion. Look also at the first page of http://people.orie.cornell.edu/shmoys/or630/notes-06/lecture...