I’M WORRIED about Murphy’s law. Not because it’s making life
difficult—I’ve got used to that—but because it isn’t making life as
difficult as it ought to. According to Murphy, anything that can go wrong, will
go wrong. So why doesn’t it seem to be happening?
Mathematics has another confounding factor: Gödel’s theorem. Seventy
years ago, Kurt Gödel demonstrated that there must be some mathematical
statements that can be neither proved nor disproved. Mathematics, he showed,
must have logical holes. Surely the combination of Gödel and Murphy ought
to add up to mathematical mayhem. Gödel says maths can go wrong, Murphy
says therefore it will. Mathematics ought to be a horrendous mess riddled with
unprovable ideas.
For some reason it isn’t like that. Mathematicians are steadily building up
their logical edifice with little, if any, mischief from Murphy. But I reckon
he’s lying in wait, concocting an especially ingenious trick. I’m even prepared
to make a guess at his hiding place.
Advertisement
Before Gödel came along, mathematics seemed an unlikely playground for
Murphy. David Hilbert, the leading mathematician of the early 20th century,
believed that the whole discipline could be based on simple logical principles,
and he led a grand project to establish this precise logical foundation.
Theorems that until then had gone unquestioned—such as 1 + 1 =
2—were attracting raised eyebrows. How do we know that? What do we mean,
for example by “1” and “+” ?
Hilbert wanted to start at the most basic level possible, with a handful of
incontrovertible statements called axioms — statements such as x + 0 = x
(adding zero doesn’t make a number bigger). He aimed to show that you could
derive all of mathematics, without leading to a contradiction, just by applying
simple logic to these axioms.
The trick, Hilbert believed, was to think of mathematics as a game played
with arbitrary symbols. Logic tells you how to manipulate the symbols. If you
can prove that the rules can never contradict themselves, everything will be
hunky-dory.
But just as Hilbert and his students were seeing the light at the end of the
tunnel, Gödel breezed by. By the time he had finished with the Hilbert
programme, he had not only switched out the light, he’d shown that there had
never been a tunnel in the first place.
Gödel turned Hilbert’s ideas against themselves. He invented a logical
framework in which an arithmetical statement can assert—in cleverly coded
form—that “this statement cannot be proved true”. If the statement is
false, then it can be proved to be true, and you have a contradiction. So it
must be true. But that means you can’t prove it.
Is there any way around this? Well, there are various ways of constructing a
logical framework for arithmetic. There is some freedom to choose your axioms
and still end up with a version of arithmetic where 1 + 1 = 2. For example, you
can start by defining addition, and use that to derive multiplication. Or you
can define multiplication and work out how to add using that.
But Gödel showed that however you set it up, your system must still
contain undecidable statements. And given such a statement, there will be a
formalisation of arithmetic in which it is provably true, another in which it is
provably false, and still others in which it remains undecidable.
Several questions have been shown to be undecidable. Among them is the
“halting problem”. Alan Turing, an English mathematician, introduced the concept
of a Turing machine—a mathematical formalisation of a digital computer.
When you run a program on a Turing machine, either it stops and spits out an
answer, or it goes on forever. For example, a program like
1. Go to line 2
2. Stop
obviously halts. Whereas
1. Go to line 1
2. Stop
does not, because it never gets to line 2. The problem is to find a
systematic method for deciding in advance whether or not a given program will
halt.
Turing proved that the halting problem is undecidable. To do so, he played
much the same game as Gödel. Assuming that the halting problem is
decidable, Turing showed that you could construct a program that stops if and
only if it does not stop. This is crazy, so the assumption is false.
The Russian mathematician Yuri Matijasevic found another undecidable problem:
is there a systematic method to decide whether or not an algebraic equation has
at least one solution in whole numbers? Essentially, his proof shows that
algebraic equations can behave like a Turing machine. Score two for Murphy.
Other examples of undecidability followed, and the score mounted steadily.
And yet none of this work had much impact on mainstream maths. Gödel’s
ideas changed the way mathematicians thought about the deep foundations of their
subject, but they didn’t have much effect on day-to-day research. This seems
odd, especially since the mainstream offers Murphy plenty of opportunities.
There are always big unsolved problems that every mathematician would give their
eye teeth to polish off.
Around 1950, for instance, three of the hottest such properties were Fermat’s
last theorem, the four-colour problem and the Kepler conjecture. The first
states that no two perfect cubes can add up to a perfect cube, and ditto for
fourth, fifth and all higher powers. The second states that every map can be
filled in with four colours in a way that always gives adjacent regions
different colours. The third says that that the most compact way to stack balls
is the way fruit sellers pile up their oranges, in overlapping hexagonal
sheets.
Triple whammy
So there we had three big, unsolved problems. And we had Gödel, telling
us that mathematical problems do not have to possess a definitive solution at
all. The opportunity for Murphy to strike seemed irresistible. Surely at least
one of those important problems would turn out to be undecidable? Somehow,
though, Murphy muffed it. The four-colour problem was proved in 1976 by Kenneth
Appel and Hermann Haken, Fermat’s last theorem succumbed to Andrew Wiles in
1994, and the Kepler conjecture was proved in 2000 by Thomas Hales. All three
conjectures turned out to be true.
Why had Murphy’s run of success ground to a halt? Well, if you look at his
early successes, a pattern emerges. They are all “meta-problems”—problems
about problems. Hilbert wanted maths to be a general method for deciding whether
any given statement is true, and Gödel proved that it can’t be. Turing
likewise demolished the possibility of a general method for answering “does this
thing ever stop?” It’s as if the significant parts of mainstream
mathematics—as opposed to meta-mathematics— are no-go areas for
Murphy. But the whole point about Murphy is that there should be no no-go
areas.
This makes a lot of mathematicians uneasy. Where are all the undecidable
problems? Why are there only a few, lurking in the meta-mathematical fringes? I
suspect the answer is that, when it comes to mathematics, Murphy is both subtle
and malicious. There is one really big unsolved problem that might be suitable
territory for Murphy to play in. Admittedly, it looks a bit like a meta-problem,
but answering it would tell us something important about lots of interesting,
specific problems. It’s of genuine interest in mainstream mathematics.
The problem I have in mind is known as “P = NP?”, and if you solve it you can
win a million dollars. The prize is one of seven on offer from the Clay
Mathematics Institute, each worth a cool million (see www.claymath.org). The
rules are strict: your solution has to be published in a major mathematical
journal and be accepted by the mathematical community for several years—so
don’t send your attempts to me.
P = NP? is simply a coded question about the efficiency of computer
algorithms. The underlying question is: how rapidly does the computational time
grow as the size of a problem gets larger? Some problems can be solved quickly
by a computer, even for large amounts of input data. By quickly, I mean that the
number of computational steps required is at most proportional to a fixed power
of the size of the problem. Such an algorithm is said to run in polynomial time,
or to be in class P.
An example is sorting a long list of words into alphabetical order. The
simplest way to do this takes a time proportional to the square of the number of
words. So sorting ten words takes four times as long as sorting five. If you
want to sort a telephone directory’s worth of names you need a pretty fast
computer, but it can be done.
A much harder task is the travelling-salesman problem. A salesman has to
visit a number of towns: in what order should he do this to minimise the total
distance travelled? One method is to consider all possible routes and simply
pick out the shortest. Trouble is, the number of routes grows faster than any
power of the number of towns. You might be able to solve it in no time for 10 or
20 towns, but for 100 towns? Forget it. And no one knows whether there is a
faster, class-P method.
What we do know about this problem is that you can check whether any given
route is the shortest relatively quickly. It’s a little like a jigsaw puzzle:
finding a solution takes a lot of work, but a quick glance is enough to tell you
whether the puzzle has been solved. How to do this for the travelling-salesman
problem isn’t quite so obvious, but you can in fact check whether a route is the
shortest in polynomial time. This puts the travelling-salesman problem in class
NP, which stands for nondeterministic polynomial time.
The question P = NP? asks whether every class-NP question is actually
class-P. In other words, if an answer to a question can be checked in polynomial
time, can it always be found in polynomial time?
At first sight, the solution to P = NP? should surely be no. Finding an
answer to something ought to be harder than checking it once someone has found
it. Yet nobody has been able to prove or disprove it, which is why there’s a
million dollars on offer.
The P = NP? problem opens up the workings of mathematics for the insertion of
a Murphic spanner, thanks to a strange phenomenon called “NP-completeness”. It
turns out that many ostensibly different NP problems are actually the same
problem coded in different ways. So a polynomial-time algorithm to solve one of
these would solve the others too. In fact, some of these NP problems encode
every NP problem. Find a polynomial-time algorithm that solves the
travelling-salesman problem, and you’ve found one that works for all NP
problems. All sorts of puzzles would suddenly become vastly easier—not
just abstruse mathematical questions but practical tasks such as data
compression and efficiently cutting shapes out of cloth or sheet metal.
Unfortunately, mathematicians have found that virtually every interesting NP
problem is NP-complete. That means if you want to solve any NP-complete problem,
you can’t use the favourite trick of turning it into a simpler one and solving
that instead, because they’re all as hard as each other.
All of which would tempt me to stick my neck out and conjecture that P = NP?
is undecidable. But remember how slippery such problems are—they can
become decidable in different versions of mathematics, depending on the set of
axioms you choose. So if P = NP? is undecidable, and you can prove that it is,
then there must be a consistent formalisation of mathematics in which P = NP. In
such a formalisation, all sorts of fascinating questions like the
travelling-salesman problem would have quick and easy answers. This would be a
mathematician’s paradise, and surely Murphy could not allow such a thing to
exist.
So what if P = NP? is indeed undecidable, but you can’t prove it—the
question of whether it is undecidable is also undecidable. At that level,
mathematicians could still find their P = NP paradise. First change the axioms
so that P = NP is probably undecidable, then change them again so it’s true.
But if Murphy’s master plan is an infinite regression of undecidability,
things look bleak. Then there is no level at which the undecidability can be
proved. An infinity of new axioms would be needed to reach P = NP, and paradise
would be truly out of reach.
If it can go meta-wrong, then it will go meta-wrong. Murphy metamurphosed.