THE P VERSUS NP PROBLEM
THE P VERSUS NP PROBLEM
It is Saturday evening and you arrive at a big party. Feeling shy,
you wonder how many people you already know 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 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. The problem of deciding whether the answer can
be quickly checked can really take much longer to solve, no matter how
clever a program we write, is considered one of the outstanding problems
in logic and computer science. It was formulated by Stephen Cook in 1971.
Mathematical Description authored by Stephen Cook
|
