The Role of Theory in Computer Science - Models of Computation: Exploring the Power of Computing - page 26

Space-time tradeoffs can also be studied with the branching program, a type of program
that permits data-dependent computations. (See Section 10.9 .) While branching programs
provide more flexibility than does the pebble game, they are worth considering only for prob-
lems in which the algorithms used involve branching and have access to an external random-
access memory to permit data-dependent reading of inputs, a strong assumption. For many
problems only straight-line programs are used, in which case the pebble game is the model of
choice.
A serious problem arises when the storage capacity of a primary memory is too small for
a problem, so that a slow secondary memory, such as a disk, must be used for intermediate
storage. This results in time-consuming input/output operations (I/O) between primary and
secondary memory. If too many I/O operations are done, the overall performance of the system
can deteriorate markedly. This problem has been exacerbated by the growing disparity between
the speed of CPUs and that of memories; the speed of CPUs is increasing over time at a greater
rate than that of memories. In fact, the latency of a disk, the time between the issuance of a
request for data and the time it is answered, can be 100,000 to 1,000,000 times the length of a
CPU cycle. As a consequence, the amount of time spent swapping data between primary and
secondary memory may dominate the time to perform computations. A second pebble game,
the red-blue pebble game , has been introduced to study this problem. (See Chapter 11 .)
The red-blue pebble game is played with both red and blue pebbles. The (hot) red pebbles
correspond to primary memory locations and the (cool) blue pebbles correspond to secondary
memory locations. Red pebbles are played according to the rules of the above pebble game.
The additional rules that apply to the red and blue pebbles allow a red pebble to be swapped
for a blue one and vice versa. In addition, blue pebbles reside only on inputs initially and
must reside on outputs finally. The number of red pebbles is limited, but the number of blue
pebbles is not.
The goal of the red-blue pebble game is to minimize the number of times that red and
blue pebbles are swapped, since each swap corresponds to an expensive input/output (I/O)
operation. Let T be the number of I/O operations and S be the number of red pebbles.
Upper and lower bounds on the exchange of S for T have been derived for a large number of
problems. For example, for the problem of multiplying two n

n matrices in about 2 n 3 steps
with the classical algorithm, it has been shown that a red-blue pebble-game strategy leads to a
product ST 2 proportional to n 6 and that this cannot be beaten except by a small multiplicative
factor.

×

1.5.3 Complexity Classes
Complexity classes provide a way to group languages of similar computational complexity. For
example, the nondeterministic polynomial-time languages ( NP ) are languages that can be
solved in time that is polynomial in the size of their input when the machine in question is
a nondeterministic Turing machine (TM). Nondeterministic Turing machines can have more
than one state that is a successor to the current state for the current input. Thus, they can
make choices between successor states. A language L is in NP if there is a nondeterministic
TM such that, given an arbitrary string in L , there is some choice of successor states for the
TM control unit that causes the TM to enter an accepting state in a number of steps that is
polynomial in the length of the input.
An NP -complete language L 0 must satisfy two conditions. First, L 0 must be in NP and
second,itmustbetruethatforeachlanguage L in NP astring x in L can be translated