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...
[ Parent
| on HN ]
There are no comments on this comment yet.