Ian Stewart's Visions of Infinity: The Great Mathematical Problems is an entertaining and fresh look at some of the most vexing problems facing the field of mathematics. We asked him to pick the hardest of the bunch, and then explain it to us so we feel smart.
Don’t worry—I’m not going to ask you to solve it. You can win a million dollars if you do, but right now it baffles the world’s top mathematicians. It may well be the trickiest, most annoying, most elusive mathematical problem ever. It’s the P/NP problem, and ironically it asks: do hard math problems actually exist?
Put that way, it’s a no-brainer. If they don’t, ninety-nine per cent of humanity is suffering from a collective delusion. Most mathematicians agree; they don’t believe there’s such a thing as a free lunch. But right now, they can’t prove they’re right.
The problem arose in computer science. We normally think of computing as a tool for understanding math, but here it’s math as a tool for understanding computing. Computers are fantastic aids to mathematical thought. Sometimes they come up with an answer in the blink of an eye, when the combined efforts of everyone on the planet using pencil and paper would take a million years. But sometimes even the fastest supercomputer fares no better than a child’s abacus.
P/NP is a math problem about how a computer solves math problems. Computers are good at some tasks, hopeless at others. The problem is not to decide which is which. It’s to prove there really is a difference.
Computers carry out lists of instructions. “Add these two numbers.” “Does this word start with B?” These lists are called algorithms. Whenever you use the Internet, or ride in an airplane, or use satnav, or write a document with a word-processor, you’re using an algorithm. It might be a math calculation, or it might log you into Twitter from the middle of Mongolia. So this area of math is actually pretty important.
What matters to users is not just the result of the algorithm, but how quickly the machine produces it. There’s a simple algorithm for writing a bestseller, for instance. Generate all possible books 100,000 words long, assess their readability, and pick the best one. But there are so many lists that this algorithm is a non-starter, however expensive your computer might be.
Algorithms that run quickly are said to be class P. The letter stands for ‘polynomial’—yes, it’s starting to sound like math now—which describes how rapidly the computational time grows as the size of the input increases. All other algorithms are not-P, and run too slowly to be useful, with a few honorable exceptions. The “write every possible book” algorithm is about as not-P as you can get. As the length of the book increases, the running time grows even faster than a population of immortal rabbits, doubling in size ever few months until they form a sphere that surrounds the Earth and expands faster than light.
“P or not-P, that is the question,” as Hamlet nearly said. We can generally find out how efficient any specific algorithm is. Where everything goes pear-shaped is when we think not of the algorithm, but the problem it solves. Could there be a quicker algorithm for the same problem? If so, the problem might be easy to solve; you’re just using the wrong method.
A problem is class P if there exists an efficient algorithm to solve it, and it is not-P if there isn’t. And there’s the rub, as Hamlet did say, and in the same speech. How can you decide? You can’t try every possible algorithm in turn—it’s like writing all possible books, but now there’s no length limit. If you find an efficient algorithm, the problem is definitely class P. But if your algorithm is inefficient... maybe a different one, which you’ve not discovered yet, is better.
Even so, we can prove beyond a shadow of doubt that some problems are not-P. “Write every possible book” is an example: whichever algorithm you use, it has to output the answer, and that takes forever. The class NP rules out silly problems like this one. It pins down the potentially hard problems that have short and snappy answers. The letters stand for “nondeterministic polynomial”, and the n-word means that you guess. Any individual guess can be checked very rapidly, but that doesn’t help you solve the problem unless you get lucky.
My bestseller algorithm is not NP. The output is gigantic, and to check that it’s right you have to read the whole thing and make sure nothing has been left out. Sensible hard problems are those with an answer that can easily be verified once you know what it is, but what’s difficult is finding the answer.
These are the NP problems that are not P problems. And that’s the million-dollar question, the P/NP problem:
Is NP different from P?
Do any problems exist where it’s easy to check a guess, but virtually impossible to find the right one? Most mathematicians expect the answer to be ‘yes’, but there’s a worry. Maybe there’s some cunning way to find the right guess really quickly, but we’re too stupid to spot it.
Think about solving a jigsaw. Getting the pieces in the right arrangement can be hard. But if someone shows you a finished puzzle, a single glance can decide whether they got it right, or there’s a glitch. So do I get my million bucks? Unfortunately not: solving a jigsaw is actually class P—it’s just a type of class P problem where the algorithm to find an answer is a lot slower than the one to check it.
There are hundreds of problems that mathematicians think ought to be NP but not P. The travelling salesman problem is one of them: what is the shortest route that visits each city on a list? (Mind you, we’re not even sure that one is NP, which is really annoying.) In every case no efficient algorithm is known and we don’t expect there to be one—but we can’t prove there isn’t. So, despite this embarrassment of riches, the P/NP problem remains wide open. It wouldn’t surprise me if it still is, a hundred years from now.
