Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a...
by jsc on Friday December 09, 2016 @02:14PM
(#13141008)
This is actually slower than previous art, but with proven complexity. Namely the algorithm in http://eprint.iacr.org/2011/474.pdf runs in time 2^0.72n and constant memory, but is heuristic only.
[ Parent
| on HN ]
Re:Faster Space-Efficient Algorithms for Subset Sum, K-Sum a...
by AstralStorm on Saturday December 10, 2016 @04:03AM
(#13144798)
Apples, oranges. We have heuristic algorithms for knapsack running in polynomial time. The trick is that because they are heuristic, they do not necessarily solve the problem.