About

The knapsack problem is a NP-hard problem, which has led to attempts to use it as the basis for public-key encryption systems. Several such attempts failed because the knapsack problem instances they produced were in fact solvable by polynomial-time algorithms.

history | show excerpt | excerpt history