                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

Feasible Computations

We want to investigate how many steps a computer can execute in a reasonable amount of time. This will give us a rough, but interesting, upper bound on how much we can expect out of an algorithm.

The basic measure of a computational step for a CPU is derived from the frequency of the crystal which provides the clock for the CPU, e.g., a 100 MHz frequency allows 100 million basic steps per second. A simple CPU instruction can be executed in such a step. Commercial workstations at present operate around 200 MHz, and super computers at less than than 400 MHz.

• So one-billionth of a second, called a nanosecond, and abbreviated ns, is shorter than the time needed to execute a basic cycle on current computers, and we will use it as a bound to the amount of time in a basic step.

• Computers can have large numbers of CPU’s working in parallel – at present one million CPU’s seems to be a safe upper bound to what is technically feasible.

• Finally let us say that a project which takes a hundred years to complete is “hopeless”.

With these numbers we can give an upper bound for the number of basic steps a computer can carry out on a particular project. (The particular numbers are not critical to our discussion – if you want to be more certain, take the thousandfold of each one.)

Now, from the simple fact that

1 year = 60^{2} × 24 × 365 seconds
= 3.1536 × 10^{7} seconds

we have the following approximate conversion of years to nanoseconds:

# years > #nanoseconds
1  3 × 10^{16}
10  3 × 10^{17}
100  3 × 10^{18} (the hopeless case)
1,000  3 × 10^{19}

and thus a project requiring

10^{25} basic steps is hopeless

(as 10^{25} > (3 × 10^{18}) × 10^{6}). Actually one could probably claim that even 10^{20} basic steps is hopeless for todays computers. In terms of powers of 2 we have

2^{85} basic steps is hopeless

as 2^{85} > 10^{25}. In particular this says that trying to compute a truth table with 85 variables is just impossible.

While we are looking at upper bounds, let us take a moment to consider the sizes of the popular bounds used in complexity theory, namely 2^{n}, 2^{2^{n}}, 2^{2^{2^{n}}}, etc.

doubly exponential: 2^{2^{7}} = 2^{128}  so 2^{2^{7}} basic steps is hopeless
3-fold exponential: 2^{2^{2^{3}}} = 2^{256} so 2^{2^{2^{3}}} basic steps is hopeless
4-fold exponential: 2^{2^{2^{2^{2}}}} = 2^{65,536} so 2^{2^{2^{2^{2}}}} basic steps is hopeless