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 packingDominating set Exact cover by 3-sets Graph 3-colorabilityCliqueHamiltonian cycleLongest path Minimum broadcast time Minimum cover Multiprocessor scheduling Partition Partition into cliques Precedence-constrained schedulingInteger linear programmingSatisfiability Subgraph isomorphism Subset-sum 3-dimensional matching Travelling salesmanRegex matching with backreferences... (hundreds more) ...Vertex cover

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