Page WhatIsPvsNPproblem

Which boxes in the picture above should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? Problems of this type are called knapsack problems. They belong to the class of NP problems, which are in general very hard to solve.

Let P be the class of problems that can be solved in polynomial time. P is a subset of NP. One of the Millenium problems is to decide whether P equals NP. Put differently, we want to know if there are problems whose answer can be quickly checked, but which require an impossibly long time to solve even on a supercomputer.

We will define the classes P and NP using Turing machines, give plenty of examples and explain why the P vs NP problem is important.

Section 1

Section 2

Comments

• Found at http://www.nist.gov/dads/HTML/npcomplete.html: