|Next||You can't get there from here||15|
It's hard to find solutions to the knapsack problem
It might take a long time
On the other hand, if someone proposes a solution, it's easy to check if it's correct
Just add up the total size and value
Problems that can be checked efficiently are said to be "in NP"
Lots and lots of problems are in NP
Knapsack problem, sorting, many many others
In fact, it takes some thought to come up with a reasonable problem that is not in NP
Because how would you be able to tell if you had a solution?
|Next||Copyright © 2005 M. J. Dominus|