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 NPBecause how would you be able to tell if you had a solution?

Next | Copyright © 2005 M. J. Dominus |