by Melvyn Bragg
Some of our listeners may have known that Carlos Frenk creates computer models of the universe. Melvyn certainly did, observing that he had ‘a hell of a reputation’.
CARLOS FRENK: I work on this day to day, and coming here allows me to step back and realise how amazing it is, what we actually do with these computers, because what we do essentially is to recreate the entire evolution of our universe. And it sounds grandiose, but it is. We now know that when the universe was very young, and I really mean very, very, very young …
MELVYN BRAGG: What’s young in your terms? I’m very suspicious of you lot with figures.
CARLOS FRENK: A decimal point and then imagine thirty-four zeros and one, that fraction of a second …
When the universe was very young, he went on, referring back to the microwave evidence, it was seeded with tiny little irregularities or quantum fluctuations. Carlos Frenk feeds these initial conditions, represented mathematically, into a computer. He then makes an assumption about what the dark matter consists of. Finally, he instructs the computer how to solve the equations of physics, Einstein’s relativity and so on, and lets the program work for months in a row. What astonishes him is that, when he makes the right assumptions about the dark matter, the models come out just like the universe in which we live.
Swiss astronomer Fritz Zwicky inferred the existence of unseen matter. He initially referred to it as ‘missing mass’ and later as dark matter.
CARLOS FRENK: I like to challenge my battle-hardened astronomy colleagues by showing them images of galaxies that came out of a computer from this process, from these quantum fluctuations to the present, alongside images of real galaxies, and I challenge them to tell me which is which and, more often than not, they fail.
As for particles that make up dark matter, there is apparently a range of possibilities with a huge spread of different masses and properties. Anne Green put forward the weakly interacting massive particles, or WIMPs for short, a term she said the astronomers had devised. This term was chosen as a corrective to the ordinary matter mentioned earlier, such as failed stars, which were known as massive astrophysical compact halo objects, or MACHOs. The WIMPs’ weak interactions with each other could explain why they have not been seen to date.
ANNE GREEN: They’re very heavy, they weigh [from] maybe a few times a proton up to 1,000 times and they’re a good dark matter candidate for two reasons. They’d be automatically produced a tiny fraction of a second after the Big Bang, in the right amount to be the dark matter. [And] they turn up in particle physics models that have been proposed for other reasons.
Carlos Frenk thought the chances are that these are very strange particles because they’re their own antiparticles, but so diffused that the particles of matter and antiparticles of dark matter never collide, except in very extreme situations such as in the centre of the Milky Way when they produce radiation. Following results from NASA’s Fermi satellite, which was sent up to look for gamma radiation, there are claims that the centre of the Milky Way is glowing in gamma rays and that this is a signal of dark matter there.
Another candidate for dark matter, before the hypothetical WIMPs, was the neutrino and, as Carolin Crawford said, at least we know the neutrino exists and fills the universe. It does not have a charge, so does not interact with radiation. If each of these tiny particles had a certain amount of mass and there were so many of them, that could account for the dark matter. The problem with this is that experiments have shown that the upper limits to their mass are too small for neutrinos to account for the dark matter.
Carlos Frenk had tested neutrinos as candidates for dark matter with his computer models in the 1980s, when this possibility was termed ‘hot dark matter’, and the universe that came out of a computer did not look anything at all like the universe in which we live. That, he said, was a big disappointment for him.
CARLOS FRENK: I was young then and cocky and I thought, ‘Right, we’ve now ruled out hot dark matter, let’s go for the next target,’ which was cold dark matter. Let’s rule that one out. That’s the way you make science, you rule things out in order to eventually be left with the correct assumption. So I set out in the 1980s to rule cold dark matter out and now, thirty-five years later, I’m still trying to do it.
Cold dark matter is a very different kind of particle and, he said, it is exactly the sort of particle that he needs to put into computer simulations to produce these faithful representations of our universe. It essentially explains everything we see on large scales; it explains something we call the cosmic web, which is the way in which galaxies are distributed in the universe, along filaments. The dark matter could still be warm, and it is very difficult to tell cold from warm, but he is continuing to try.
CARLOS FRENK: To me, the discovery of the dark matter would be an advance to human knowledge on the same level as the discovery of Darwinian evolution.
P VS NP
The problem of P versus NP is so difficult to solve that there is a $1 million prize on offer from the Clay Mathematical Institute for the first person to come up with a solution. At its heart is the question: are there problems for which the answers can be checked by computers but not found in a reasonable time or can all answers be found easily as well as checked if only we knew how? It has intrigued mathematicians and computer scientists since Alan Turing in the 1930s found that some programs, given a problem, could run indefinitely without finding the answer. That is as true of today’s super computers as it was in his day. Resting on P versus NP is the safety of online banking and all online transactions that are currently secure. If access can be found as easily as checked, computers could crack passwords in moments, and the chance to solve thousands of practical problems would also be in sight.
With Melvyn to discuss (but not perhaps solve) the problem of P versus NP were: Colva Roney-Dougal, reader in pure mathematics at the University of St Andrews; Timothy Gowers, Royal Society research professor in mathematics at the University of Cambridge; and Leslie Ann Goldberg, professor of computer science and fellow of St Edmund Hall, Oxford.
The Pilot ACE was one of the first computers built in the United Kingdom in the early 1950s.
Colva Roney-Dougal began by taking us back to the work of Alan Turing (1912–54), who was trying to solve some problems in the foundations of mathematics. He started thinking about how he could define whether or not it was possible to solve a problem, and this led him, at the age of twenty-two, to invent our modern notion of a computer. He defined an abstract machine, that we now call a Turing machine, and said it should be able to read input, it should be able to write output and it should be able to decide what to do, based only on what state it was in then and what symbol it was looking at. This was an imaginary machine, but he soon realised something important.
COLVA RONEY-DOUGAL: One such machine can pretend to be any other machine, you can just give it the description of the other machine and it can simulate that machine. So that meant that we’ve only ever needed one mathematical model of a computer ever since.
Algorithms were to be part of the studio discussion, and Colva Roney-Dougal described these as a collection of steps for solving a problem. An advantage of calling these an algorithm rather than just a sequence of instructions is the idea that, within an algorithm, you might want to loop. For example, a good recipe is an algorithm, if it is well written and gives clear, unambiguous instructions, such as ‘dice the onions, fry them for ten minutes over medium heat’. That said, normally in a cooking recipe, if it turns out that you have burnt the onions, you might need to go back to the beginning and start again.
COLVA RONEY-DOUGAL: Whereas with a computer algorithm, I might be wanting to do something like find a number in a sorted list of numbers and the instruction might be: ‘Look at the middle number, is it bigger or smaller than the one you want? If it’s bigger than the one you want, look at the middle of the next step down.’ It’s repeating there, ‘Keep looking in the middle and going bigger or smaller depending on the an
swer.’ You don’t necessarily, immediately, know how many steps it’s going to take.
That established, it was for Tim Gowers to explain what lay behind the letters P and NP. P stands for polynomial and NP for non-deterministic polynomial, for reasons he said he would spare us for the sake of simplicity and brevity. When people started to build actual computers rather than Turing’s imaginary ones, they realised that something was not as expected. At first, they looked at whether there was an algorithm for solving a problem, and then they slightly changed focus to see if there was an algorithm or systematic procedure that could solve a problem in a reasonable amount of time.
TIM GOWERS: It turns out that there are quite a lot of problems for which it’s very easy to write down an algorithm. The only drawback with the algorithm is that, if you program your computer to run the algorithm, it would take a trillion years or something like that.
And, if you have got something as slow as that, then you might as well just not have an algorithm. Roughly speaking, he said, ‘P stands for the class of problems for which there is a practical algorithm, an algorithm that can run in a reasonable time.’ This is not exactly the technical definition, but it is the main point, so we can think of P as standing for practical instead of exponential and impractical. An example of a polynomial time algorithm is long multiplication. If you take two numbers of 100 digits, then, to multiply those two numbers together, the number of steps will be about a 1002, roughly speaking, because each digit of one number has to be multiplied by each digit of the other number. That will be a polynomial time algorithm. An exponential one would be something where, as the input increases in size, the time it takes doubles and very rapidly will just blow up out of control. Exponential time algorithms will be ones that will take billions of years. Checking an answer to see if it is right is a slightly different thing, and that is where NP comes into all this.
TIM GOWERS: There are certain problems that are search problems, where you’re trying to find something, and you can think of it as a sort of a needle in a mathematical haystack. And sometimes it’s easy to check an answer if someone tells you, ‘I think this is the answer,’ and then you can go away and do a simple calculation and verify that it really is the answer. If that’s the case, we say that the problem’s an NP. P are things that are easy to do, full stop, and NP are things that are easy to check as long as somebody gives you a massive hint.
With the complex problems, so far unresolved and of interest, though, it appears it is slightly fantastical to talk of someone giving you a massive hint that could be checked and then found to be correct. That person is unlikely to be in a position to give that hint. Broadly speaking, exponential means hopelessly impractical.
In practice, there are workarounds for some of these exponential problems. As Leslie Goldberg explained, the obvious algorithm is exponential for most of the problems that she looks at, with exponentially many possibilities, but, for some problems, there is a clever way to narrow them down and find the right one. For example, there is one called the matching problem. If you want to find people who are compatible and put them together in a team so that everyone is with someone and no one is left out, then if you simply look at how many pairings there are, the problem would be exponential, as 100 people allow for more possibilities than there are atoms in the universe.
LESLIE GOLDBERG: An exponential ‘dumb’ algorithm might just consider every possibility and say: ‘Oh, is this possibility good – are all the people that were paired compatible? No? Let’s try the next one. No, let’s try the next one.’ That’s ridiculous. But this is actually an easy problem because we do know a polynomial time algorithm and we’ve even known it since the 1960s due to Jack Edmonds. So that’s an easy problem.
She commented that it would take more than the whole programme to explain how that polynomial time algorithm does something else and manages to find a good pairing, but she told us that it does not just look at every possibility but rather cleverly constructs the best one.
Alan Turing introduced the standard computer model in computability theory in 1936.
The next step in this discussion was to look at factorisation, which Colva Roney-Dougal described as relying on ‘a lovely fact about whole numbers that’s been known at least since the Greeks if not before’, namely that there are prime numbers, which are numbers that can only be divided by one and themselves. It transpires that any whole number can be divided up into primes and that, if those primes are to come out in an increasing order, then there is only one way to do it. For example, twelve goes to ‘2 x 2 x 3’. That is easy enough for small numbers, but, for large numbers, perhaps those with 200 digits, it is very, very hard. This factorisation of primes has a property that, while it is so hard to find the answer, it is easy to check it by multiplying the primes, and that is important.
COLVA RONEY-DOUGAL: All modern cryptography is essentially based on the fact that, if I multiply together two very big primes, that’s easy to do. If I just give you the answer, you can find the two very big primes easily.
This factorisation of primes, Tim Gowers said, was a very good example of an NP problem where it is easy to check but very, very hard to solve. After this, and helping us move towards an understanding, he said there was then something that does not apply to this factorisation problem, but which he described as ‘a bit of a miracle’, the NP-complete problem, which Leslie Goldberg was about to explain.
TIM GOWERS: There are a lot of NP problems that turn out to be of equivalent difficulty in the following sense: that, if you’ve got a good method for solving one of them, then, by a completely nonobvious process, you can convert it into a good way of solving one of the other problems.
MELVYN BRAGG: Leslie Goldberg, give us the travelling salesman problem.
This is the problem where there is one travelling salesman who has to visit several cities that are some distance apart, and the salesman has to work out the shortest route by which to visit each city only once, and then come back to the start.
LESLIE GOLDBERG: That is an NP-complete problem or, more formally, the decision version of it is, but, anyway, it’s as hard as everything in NP. So the amazing thing is, if you could solve that problem, you could solve factoring and you could also solve every other problem in NP, and there are thousands of them. DNA sequencing is one of the applications of that. I talk about cities but you could say a city is a DNA fragment.
Prompted by Melvyn to say more about why this problem is so very difficult, Leslie Goldberg emphasised that there are exponentially many possibilities, so a ‘dumb’ algorithm certainly would not work. Besides, not only do we not have a ‘clever’ algorithm, we do not even know if one exists. Perhaps seeing a look on Melvyn’s face that he was unconvinced, Tim Gowers suggested that he could think of it not as five cities but as 200, and then it might be more obviously hard.
Many of these problems may appear dissimilar, but they can have similar solutions. Colva Roney-Dougal offered that of the seating plan for a large wedding.
MELVYN BRAGG: What’s large?
COLVA RONEY-DOUGAL: Let’s say 150 guests sitting down to dinner, and you’ve got a big long table to sit them all down, and you know that quite a few of your guests absolutely loathe each other; they must not be sat next to each other.
MELVYN BRAGG: So this is a typical wedding.
This one turns out to be another one of these problems that is hard to solve but easy to check. If the plan is right, the couple can look around the room and see whether anyone is sitting next to anyone they hate. But to do that from scratch with 100 people, let alone 150, would offer more permutations than there are electrons in the solar system. This is essentially the same as the travelling salesman problem, which is NP-complete, and, if someone can find a way of solving the one, then that can be applied to the other. Tim Gowers added that mathematicians strip away the details of practical problems, such as seating plans and sales trips, and turn them into abstract mathematical problems. These two problems, ma
thematically, are ones of networks, with nodes and links between the nodes, where the nodes could be cities or wedding guests and the links could be roads or antipathies.
TIM GOWERS: Once we’ve turned it into an abstract problem, we can then take it a little bit outside the realm of the practical, we can make these networks get larger and larger. And actually, when we study abstractly, we think we’ve got a network with N nodes, where we think of N as just some very large number and we’re interested in how the difficulty of solving the abstract problem scales with N. Once you’ve slightly left the real world behind, I think it then becomes more plausible that these problems should be very hard.
There are fine lines between problems that can be solved and those that become unsolvable. Leslie Goldberg referred to the pairing exercise she mentioned earlier. Forming twos is relatively easy, but, when that moves to forming threes, it becomes exponentially problematic. Tim Gowers added that what we have is a very precisely defined class of problems, called the NP problems, and, inside those, there is another very precisely defined sub-class of problems, the NP-complete problems. There is a well-understood method of reducing any NP problem to any given NP-complete problem, so, if we can solve the NP-complete problem, then we can solve the NP problem.
TIM GOWERS: If one could prove that P does equal NP, that would be saying that things that are easy to check are actually easy to find, [that] would be enormous because you’d suddenly be able to solve a vast number of problems that, at present, we think you can’t solve.
By and large, it seems that people do not think that it is going to be the case that P equals NP, but there is still a tantalising possibility that somebody could just come up with an algorithm for the travelling salesman problem that would revolutionise the way we find algorithms in general. Tantalising it may be, but that is out of reach for now. Leslie Goldberg would not say that mathematicians have hit a brick wall as there is progress, even if that is slow. The problem has been known about since 1971, when people probably thought it would be solved in a year or two.
