\newpage\subsection {Fast and Lean Computations.\label{paral}}

Based on [Chandra, Stockmeyer 1976], we now reduce the computations with {\em
large} time and {\em small} space to parallel ones (PPM implemented by sorting
networks) with {\em large} space and {\em small} time, and vice versa.

\paragraph{Parallelization.}

Suppose Professor has in his office a program (for a Small Machine with linear
space and exponential time) solving the next exam problems. You break into his
office shortly before the test and get the tape. Your time is very limited,
insufficient to run the program - but wait! - also in the office you find the
password that gains you access to a {\em really} Big Machine, one with
essentially unlimited space resources (exponential number of parallel
processors, memory, etc.). How can you, the devious student, exploit in small
time this vast resource to solve the exam?

	Generate simultaneously all possible configurations of the Small
Machine with linear memory space, each as a separate process. There will be
$M=n^{O(n)}$ of these configurations/processes, as there are $n^{O(n)}$
possible graphs with $n$ nodes and $O(n)$ edges. Each configuration/process $x$
computes a pointer $x\to x'$, where $x$ and $x'$ are successive configurations
of Professor's Small Machine. Now, each process gets a copy of its
successor's successor pointer: $x\to x'\to x''$ leads to $x\to x''$. Next, the
single step pointers are erased and the procedure repeats for the 4-step
pointers, 8-step pointers, etc.

If the Professor's Small Machine halts, then it cannot repeat a configuration
and must stabilize in time $<M$. So, our pointer-compressing procedure will
take at most $\log M=O(n\log n)$ steps, which is only P-time. Once it is
complete, we need only take the input configuration for the test, and it will
have a pointer to the answer configuration. The {\em volume} (time $\ast$
space) of computation is still vast. There is no way known to reduce volume to
a polynomial, but you see how we can trade space for time.

\subsubsection*{Computing in Tight Space: a Pebble Game.\label{pebble}}

Consider now a {\em large} array $M$ of interacting automata running in
parallel for a P-time.

\noindent\parbox{295pt} {We want to compute in polynomial space its output,
however long it takes. Assume $M$ to be a fixed connection network (which, we
know, can simulate any PPM). The directed, acyclic graph at the right serves as
a space-time diagram of the operation of $M$: rows represent time steps. Each
node stores an {\em (event)}, i.e. the state of a particular automaton at a
particular time. Each event is a function of its parents i.e.\ the events of
the previous step in the automaton and its ($O(1)$, say, 3) neighbors. Here
$a_t, b_t, c_t$ and $d_t$ represent the states at time $t$ of $b$ and its
neighbors which determine $b_{t+1}$.}\hspace{1pc}
 \parbox{160pt} {\vector(1,0){128} space\\\mbox {\raisebox{4pc}
{\vector(0,-1){87}}\hspace{-10pt}\raisebox{-4pc} {time}\parbox{2in}
{\makebox[2in] { (input) \dotfill}
 \makebox[2in] {\vdots\hfill\vdots} \makebox[2in]{\dotfill\ $a_t$
	\dotfill\dotfill\ $b_t$ \dotfill\ $c_t$ \dotfill\ $d_t$ \dotfill}
\makebox[2in] {\dotfill\ $b_{t+1}$ \dotfill} \makebox[2in] {\vdots\hfill\vdots}
\makebox[2in] {\dotfill\ (output) \dotfill}}}}

\vspace{9pt} We will compute $M$'s output (in the {\em central} automaton $O$)
assuming the computation time $n$ (i.e. the depth of the graph) is {\em small}.
Each node can be described by a triplet ($i,t,s$), where $i$ is the position of
the automaton; $s$ its state; $t$ the time. The length of this triplet is {\em
small}: $|s|=O(1)$; $|t|= O(\log (n))$. How long $i$'s may we need? An
automaton can only be relevant if it has time to propagate its information to
$O$, i.e. is $\le n$ links away from it. There are only $3^n$ of those. So:
$|i|= O(\log(3^n)) = O(n)$.

We therefore can store each event in a {\em small} space. But it doesn't help
if we need to store a {\em large} number of events. To know how many events we
need to store we consider the {\em Pebble Game} with the following rules:
 The goal is to pebble (put a pebble in) a marked node O of a digraph;
 one can only pebble a node if all its parents are pebbled;
 there are k pebbles, they can be removed and reused.

Note that input nodes have no parents and can always be pebbled. You can win
with $k=O(dn)$ ($d$: degree of the graph; $n$: its depth). The proof is by
induction. Suppose you can pebble any node at level $t\ge0$ with $1+(d-1)t$
pebbles. Then you can pebble any node at level $t+1$ with $(d-1)t + d =
1+(d-1)(t+1)$ pebbles. You just pebble each of the node's parents, leave a
pebble there and reuse the rest of the pebbles for the next parent. Finally you
put a pebble in the node itself. However, the time needed to pebble this graph
may be {\em large} (you may have to traverse all descending paths).

Pebbling a node corresponds to computing an event in our diagram. Each event
can be computed once its parents' are. $k$ is actually the number of events we
may have to store simultaneously. Since we can pebble the graph with $3n$
pebbles we can solve the problem in space $3n\ast|(i,t,s)|$. We transformed
{\em large} space, {\em small} time into {\em small} space, {\em large} time.
But the volume (space$\ast$time) is still {\em large}.