| Next | You can't get there from here | 17 |
Many smart people have worked very hard on solving the knapsack problem
Also on a lot of not-obviously-related problems
Bin packing
Clique
Dominating set
Exact cover by 3-sets
Graph 3-colorability
Hamiltonian cycle
Integer linear programming
Longest path
Minimum broadcast time
Minimum cover
Multiprocessor scheduling
Partition
Partition into cliques
Precedence-constrained scheduling
Regex matching with backreferences
Satisfiability
Subgraph isomorphism
Subset-sum
3-dimensional matching
Travelling salesman
Vertex cover
... (hundreds more) ...
Nobody knows an efficient algorithm for any of these
But an efficient algorithm for "Knapsack" could be turned into an efficient algorithm for all of them
And it could be turned into an efficient algorithm for all problems in NP!
We say that Knapsack is NP-Complete
So are all those other problems, it turns out
| Next | ![]() |
Copyright © 2005 M. J. Dominus |