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