News for hackers. Stuff that matters.
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.
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.