3 ms·
This is actually slower than previous art, but with proven complexity. Namely the algorithm in http://eprint.iacr.org/2011/474.pdf http://eprint.iacr.org/2011/4
by jsc 10y ago
This is actually slower than previous art, but with proven complexity. Namely the algorithm in http://eprint.iacr.org/2011/474.pdf http://eprint.iacr.org/2011/474.pdf runs in time 2^0.72n and constant memory, but is heuristic only.
- AstralStorm 10y agoApples, 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.