It's not often that results from conferences on mathematics make
the news, but that's precisely what happened last month at the
annual Crypto conference in Santa Barbara, CA when researchers
from France, Israel, and China all showed that they had
discovered flaws in a widely used algorithm called MD5an
algorithm that I
wrote
about in some detail last month. The "when life gives you lemons,
make lemonade" message that came out of the conference was that
this process of breaking codes and developing even stronger ones
is all part of the cryptographerâ€™s game.
But what if a fundamental breakthrough in mathematics rendered
useless all of the fancy encryption that the world now depends
upon?
For more than 30 years, mathematicians have sought in vain the
answer to a simple problem in theoretical computer science. The
problem is what's known as an open questionit's a simple
equation that is either true or false. It can't be both.
The problemindependently formalized by the mathematicians
Stephen Cook and Leonid Levin in 1971remains one of the central
unsolved questions of modern mathematics. It is a problem about
other problems.
Cook and Levin asked whether there exist mathematical puzzles
that are hard to solve, but that have solutions that are easy to
verify. As the problem is commonly phrased, the mathematicians
asked whether P is equal or not equal to NP.
P is the set of problems that are easy to solve. Strictly
speaking, it is the set of problems that can be solved in
"polynomial" timethat is, in an amount of time that is roughly
proportional to the size of the problem's description. Most of
these problems are so easy, in fact, that we hardly even consider
them to be problems at all. For example, multiplying two numbers
together is a P problem: the solution can be found in polynomial
time. Another P problem is searching for a book that's lost in
your house. Even if all of your books are packed away in boxes in
your basement, it's still an "easy" problem to solve, at least by
mathematical standards: just open up every box and look. It might
take you days, but if you can do a thorough search, you will find
the book.
NP problems, on the other hand, are hard problems. NP standards
for "nondeterministic polynomial"it's a formalism that
describes a kind of computer that can't be built, but that can be
mathematically modeled. An NP computer can simultaneously try
every possible solution to a problem and recognize which one is
correct.
It turns out that NP computers are really good at solving any
kind of problem where the answer can be found only by searching.
One of the best examples of these problems today is code
breaking. Say the FBI raids a terrorist hideout and grabs a
laptop with encrypted files on it. The only feasible way to
decrypt the data today is to try every possible encrypt key,
hoping that one will work. A small network of modern computers
can try every possible 40bit key in just a few weeks. But a
technically advanced terrorist would be more likely to use
128bit encryption. And cracking a single 128bit key, even
harnessing the power of every computer on the planet, could take
thousands of billions of years. For all practical purposes, it's
impossible to break such a code, because today's computers can
only try one or a few keys at a time.
An NP computer, if one existed, could try all of the possible
keys at the same time, and recognize instantly which key was
correct. Code breaking is an NP problem.
Factoring is another NP problem. Although there are various
techniques for factoring large numbers, all of them involve
searching through large numbers of, well, numbers. But an NP
computer could simultaneously try to multiply every number with
every other number and somehow pick out the pair of numbers that
yielded as a product the number that the computer was told to
factor. The difficulty of factoring large numbers is at the basis
of the RSA encryption algorithm, which is built into practically
every Web browser and is the basis of most ecommerce.
As described above, NP computers seem like magical things that
could never exist today. But that might not be the case. It's
easy to see that there exist many NP problems, includingâ€”code
breakingand factoring. But nobody has ever been able to
mathematically prove that it's impossible to solve all NP
problems in polynomial time on an ordinary computerin other
words, that P is not equal to NP.
Many experts now believe, however, that it's just a matter of
time before the question will be resolved.
One mathematician who was willing to back that belief with gold
is Michael Sipser, who this month becomes the new head of the MIT
Mathematics Department. Back when he was a graduate student at
the University of California, Berkeley, Sipser went so far as to
bet a fellow graduate student an ounce of gold that by the end of
the twentieth century, P would be found to be not equal to NP.
Sipser lost, of course.
As it turns out, the graduate student that accepted Sipser's
offer was Len Adelmanthe "A" in RSA. "I thought then that the
problem was just not ripe for any resolution," says Adelman,
explaining why he accepted Sipser's wager.
After he made the bet, Sipser ended up becoming a professor of
mathematics at MIT and taught MIT's course on the theory of
computation. He enjoyed the course so much that he wrote an
introductory textbook that has become one of the subject's
bibles. And he has published extensively on the history of the P
vs. NP question.
There is a lot riding on the answer to that question. That's
because what Cook and Levin realized simultaneously back in 1971
is that there exists a large number of NP problems that can be
thought of as "perfect" or "complete." Each of these socalled
NPcomplete problems encompasses everything that it means to be
an NP problem. That means that if a solution for any NPcomplete
problem could be found that could be solved in polynomial time,
then a shortcut solution could be found for every NP problem.
In practical terms, that would spell the end of encryption as we
know it. The Internet would be vulnerable to hackers and computer
viruses.
As the twentieth century neared its conclusion, it became clear
to Sipser that nobody was going to find a solution anytime soon.
This left the matter of the bet."There was a little bit of a
controversy as to when the entry of the century was," he recalls.
"Was it January 1, 2000, or January 1, 2001? I decided not to
quibble because it didn't look like [a solution] was imminent. So
somewhere early in 2000, I bought an American Gold EagleI spent
an extra $10 to make it a Year 2000 Gold Eagleand I sent it to
him."
Adelman had long since left his professorship at MIT and taken up
residence at the University of Southern California, where he
works on cryptography and DNAbased computers. Reached by email,
Adelman confirmed that he received the gold coin.
Today, however, there is a lot more than an ounce of gold riding
on the question. Shortly after Sipser sent Adelman the coin, the
Clay Mathematics Institute of Cambridge, MA, named the P and NP
question as one of the Institute's seven "Millennium Problems."
The institute set aside $7 million, with a $1 million prize
offered to the person (or machine) that can solve each problem.
Adelman thinks that we'll be waiting for the solution for a long
time. Resolving the question of P and NP, he says, "would require
new and brilliant ideas and not routine incremental progress.
From my perspective, we are no nearer to solving the problem now
that we were when bellbottom pants were cool."
