David Deutch - The Fabric of Reality

What counts for ‘tractability’, according to the standard definitions, is not the actual time taken to multiply a particular pair of numbers, but the fact that the time does not increase too sharply when we apply the same method to ever larger numbers. Perhaps surprisingly, this rather indirect way of defining tractability work very well in practice for many (though not all) important classes of computational tasks. For example, with multiplication we can easily see that the standard method can be used to multiply numbers that are, say, about ten times as large, with very little extra work. Suppose, for the sake of argument, that each elementary multiplication of one digit by another takes a certain computer one microsecond (including the time taken to perform the additions, shift and other operations that follow each elementary multiplication. When we are multiplying the seven-digit numbers 4,220,851 an 2,594,209, each of the seven digits in 4,220,851 has to be multiplied by each of the seven digits in 2,594,209. So the total time require for the multiplication (if the operations are performed sequential) will be seven times seven, or 49 microseconds. For inputs rough ten times as large as these, which would have eight digits each, the time required to multiply them would be 64 microseconds, an increase of only 31 per cent.

Clearly, numbers over a huge range — certainly including any numbers that have ever been measured as the values of physical variables — can be multiplied in a tiny fraction of a second. So multiplication is indeed tractable for all purposes within physics (or, at least, within existing physics). Admittedly, practical reasons for multiplying much larger numbers can arise outside physics. For instance, products of prime numbers of 125 digits or so are of great interest to cryptographers. Our hypothetical machine could multiply two such prime numbers together, making a 250-digit product, in just over a hundredth of a second. In one second it could multiply two 1000-digit numbers, and real computers available today can easily improve upon those timings. Only a few researchers in esoteric branches of pure mathematics are interested in performing such incomprehensibly vast multiplications, yet we see that even they have no reason to regard multiplication as intractable.

By contrast, factorization, essentially the reverse of multiplication, seems much more difficult. One starts with a single number as input, say 10,949,769,651,859, and the task is to find two factors — smaller numbers which when multiplied together make 10,949,769,651,859. Since we have just multiplied them, we know that the answer in this case is 4,220,851 and 2,594,209 (and since those are both primes, it is the only correct answer). But without such inside knowledge, how would we have found the factors? You will search your childhood memories in vain for an easy method, for there isn’t one.

The most obvious method of factorization is to divide the input number by all possible factors, starting with 2 and continuing with every odd number, until one of them divides the input exactly. At least one of the factors (assuming the input is not a prime) can be no larger than the input’s square root, and that provides an estimate of how long the method might take. In the case we are considering, our computer would find the smaller of the two factors, 2,594,209, in just over a second. However, an input ten times as large would have a square root that was about three times as large, so factorizing it by this method would take up to three times as long. In other words, adding one digit to the input would now triple the running time. Adding another would triple it again, and so on. So the running time would increase in geometrical proportion, that is, exponentially, with the number of digits in the number we are factorizing. Factorizing a number with 25-digit factors by this method would occupy all the computers on Earth for centuries.

The method can be improved upon, but all methods of factorization currently in use have this exponential-increase property. The largest number that has been factorized ‘in anger’, as it were — a number whose factors were secretly chosen by mathematicians in order to present a challenge to other mathematicians — had 129 digits. The factorization was achieved, after an appeal on the Internet, by a global cooperative effort involving thousands of computers. The computer scientist Donald Knuth has estimated that the factorization of a 250-digit number, using the most efficient known methods, would take over a million years on a network of a million computers. Such things are difficult to estimate, but even if Knuth is being too pessimistic one need only consider numbers with a few more digits and the task will be made many times harder. This is what we mean by saying that the factorization of large numbers is intractable. All this is a far cry from multiplication where, as we have seen, the task of multiplying a pair of 250-digit numbers is a triviality on anyone’s home computer. No one can even conceive of how one might factorize thousand-digit numbers, or million-digit numbers.

At least, no one could conceive of it, until recently.

In 1982 the physicist Richard Feynman considered the computer simulation of quantum-mechanical objects. His starting-point was something that had already been known for some time without its significance being appreciated, namely that predicting the behaviour of quantum-mechanical systems (or, as we can describe it, rendering quantum-mechanical environments in virtual reality) is in general an intractable task. One reason why the significance of this had not been appreciated is that no one expected the computer prediction of interesting physical phenomena to be especially easy. Take weather forecasting or earthquake prediction, for instance. Although the relevant equations are known, the difficulty of applying them in realistic situations is notorious. This has recently been brought to public attention in popular books and articles on chaos and the ‘butterfly effect’. These effects are not responsible for the intractability that Feynman had in mind, for the simple reason that they occur only in classical physics — that is, not in reality, since reality is quantum-mechanical. Nevertheless, I want to make some remarks here about ‘chaotic’ classical motions, if only to highlight the quite different characters of classical and quantum unpredictability.

Chaos theory is about limitations on predictability in classical physics, stemming from the fact that almost all classical systems are inherently unstable. The ‘instability’ in question has nothing to do with any tendency to behave violently or disintegrate. It is about an extreme sensitivity to initial conditions. Suppose that we know the present state of some physical system, such as a set of billiard balls rolling on a table. If the system obeyed classical physics, as it does to a good approximation, we should then be able to determine its future behaviour — say, whether a particular ball will go into a pocket or not — from the relevant laws of motion, just as we can predict an eclipse or a planetary conjunction from the same laws. But in practice we are never able to measure the initial positions and velocities perfectly. So the question arises, if we know them to some reasonable degree of accuracy, can we also predict to a reasonable degree of accuracy how they will behave in the future? And the answer is, usually, that we cannot. The difference between the real trajectory and the predicted trajectory, calculated from slightly inaccurate data, tends to grow exponentially and irregularly (‘chaotically’) with time, so that after a while the original, slightly imperfectly known state is no guide at all to what the system is doing. The implication for computer prediction is that planetary motions, the epitome of classical predictability, are untypical classical systems. In order to predict what a typical classical system will do after only a moderate period, one would have to determine its initial state to an impossibly high precision. Thus it is said that in principle, the flap of a butterfly’s wing in one hemisphere of the planet could cause a hurricane in the other hemisphere. The infeasibility of weather forecasting and the like is then attributed to the impossibility of accounting for every butterfly on the planet.