I鈥橫 WORRIED about Murphy鈥檚 law. Not because it鈥檚 making life
difficult鈥擨鈥檝e got used to that鈥攂ut because it isn鈥檛 making life as
difficult as it ought to. According to Murphy, anything that can go wrong, will
go wrong. So why doesn鈥檛 it seem to be happening?
Mathematics has another confounding factor: G枚del鈥檚 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鈥檛 like that. Mathematicians are steadily building up
their logical edifice with little, if any, mischief from Murphy. But I reckon
he鈥檚 lying in wait, concocting an especially ingenious trick. I鈥檓 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鈥攕uch as 1 + 1 =
2鈥攚ere 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鈥檛 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鈥檇 shown that there had
never been a tunnel in the first place.
G枚del turned Hilbert鈥檚 ideas against themselves. He invented a logical
framework in which an arithmetical statement can assert鈥攊n cleverly coded
form鈥攖hat 鈥渢his 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鈥檛 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
鈥渉alting problem鈥�. Alan Turing, an English mathematician, introduced the concept
of a Turing machine鈥攁 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鈥檚
ideas changed the way mathematicians thought about the deep foundations of their
subject, but they didn鈥檛 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鈥檚
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鈥檚 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鈥檚 run of success ground to a halt? Well, if you look at his
early successes, a pattern emerges. They are all 鈥渕eta-problems鈥濃�攑roblems
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鈥檛 be. Turing
likewise demolished the possibility of a general method for answering 鈥渄oes this
thing ever stop?鈥� It鈥檚 as if the significant parts of mainstream
mathematics鈥攁s 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鈥檚 of genuine interest in mainstream mathematics.
The problem I have in mind is known as 鈥淧 = 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鈥攕o
don鈥檛 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鈥檚 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鈥檚 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鈥檛 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鈥檚 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 鈥淣P-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鈥檝e found one that works for all NP
problems. All sorts of puzzles would suddenly become vastly easier鈥攏ot
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鈥檛 use the favourite trick of turning it into a simpler one and solving
that instead, because they鈥檙e 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鈥攖hey 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鈥檚 paradise, and surely Murphy could not allow such a thing to
exist.
So what if P = NP? is indeed undecidable, but you can鈥檛 prove it鈥攖he
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鈥檚 true.
But if Murphy鈥檚 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.