|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|