|
|
| -=The
P versus NP Problem=- |
| It is Saturday
evening and you arrive at a big party. Feeling shy, you wonder whether
you already know anyone in the room. Your host proposes that you
must certainly know Rose, the lady in the corner next to the dessert
tray. In a fraction of a second you are able to cast a glance and
verify that your host is correct. However, in the absence of such
a suggestion, you are obliged to make a tour of the whole room,
checking out each person one by one, to see if there is anyone you
recognize. This is an example of the general phenomenon that generating
a solution to a problem often takes far longer than verifying that
a given solution is correct. Similarly, if someone tells you that
the number 13,717,421 can be written as the product of two smaller
numbers, you might not know whether to believe him, but if he tells
you that it can be factored as 3607 times 3803 then you can easily
check that it is true using a hand calculator. One of the outstanding
problems in logic and computer science is determining whether questions
exist whose answer can be quickly checked (for example by computer),
but which require a much longer time to solve from scratch (without
knowing the answer). There certainly seem to be many such questions.
But so far no one has proved that any of them really does require
a long time to solve; it may be that we simply have not yet discovered
how to solve them quickly. Stephen Cook formulated the P versus
NP problem in 1971. |
|
