If only space is under consideration, and one is OK with a constant-factor slackness, then TMs and RAMs are equivalent; much like
is invariant under power changes in time. In a sense, changing the space by a constant factor is like changing the time by a power; from this point of view the equivalence is not surprising.
We shall consider both space bounds bigger than the input length and smaller. For the latter, we have to consider the input separately. The machine should be able to read the input, but not write on its cells. One way to formalize this is to consider 2TMs, where one tape holds the input and is read-only. The other is a standard read-write tape.
We investigate next some basic relationship between space and time.
A non-trivial saving is given by the following theorem.
This result is not specific to MTMs but can be proved for other models such as RAMs.
Just like for Time, for space one has universal machines and a hierarchy theorem. The latter implies
. Hence, analogously to the situation for Time and NTime (section º5.1), we know that at least one of the inclusions above between L and PSpace is strict. Most people seem to think that all are, but nobody can prove that any specific one is.
The strongest available impossibility result for branching programs is the following.
Computing with severe space bounds, as in L, seems quite difficult. Also, it might be somewhat less familiar than, say, computing within a time bound. It turns out that L is a powerful class capable of amazing computational feats that challenge our intuition of efficient computation. Moreover, these computational feats hinge on deep mathematical techniques of wide applicability. We hinted at this in Chapter 1. We now give further examples. At the same time we develop our intuition of what is computable with little space.
To set the stage, we begin with a composition result. In the previous sections we used several times the simple result that the composition of two maps in P is also in P. This is useful as it allows us to break a complicated algorithm in small steps to be analyzed separately – which is a version of the divide et impera paradigm. A similar composition result holds and is useful for space, but the argument is somewhat less obvious.
A first example of the power of L is given by its ability to perform basic arithmetic. Grade school algorithms use a lot of space, for example they employ space
to multiply two
-bit integers.
Iterated multiplication is of particular interest because it can be used to compute “pseudorandom functions.” Such objects shed light on our ability to prove impossibility results via the “Natural Proofs” connection which we will see in Chapter ??.
Proving 4. and 5. is more involved and requires some of those deep mathematical tools of wide applicability we alluded to before. Division can be computed once we can compute iterated multiplication. In a nutshell, the idea is to use the expansion
We omit details about bounding the error. Instead, we point out that this requires computing powers
which is an example of iterated multiplication (and in fact is no easier).
So for the rest of this section we focus on iterated multiplication. Our main tool for this the Chinese-remaindering representation of integers, abbreviated CRR.
To compute iterated multiplication the idea is to move to CRR, perform the multiplications there, and then move back to standard representation. A critical point is that each coordinate in the CRR has a representation of only
bits, which makes it easy to perform iterated multiplication one multiplication at the time, since we can afford to write down intermediate products.
Now we explain how steps 1, 2, and 3 can be implemented in L. Step 4 can be implemented in L too, but showing this is somewhat technical due to the computation of the numbers
in Theorem 7.6. However these numbers only depend on the input length, and so we will be able to give a self-contained proof that iterated multiplication has branching programs of size
.
Step 3
This is a smaller version of the original problem: for each
, we want to compute
from
. However, as mentioned earlier, each
is at most
in magnitude and thus has a representation of
bits. Hence we can just perform one multiplication at the time in L.
Step 4
By Theorem 7.6, to convert back to standard representation from CRR we have to compute the map
Assuming we can compute the
, this is just multiplication and iterated addition, which are in L by Theorem 7.5.
Putting the steps together
Combining the steps together we can compute iterated multiplication in L as long as we are given the integers
in Theorem 7.6.
In particular, because the
only depend on the input length, but not on the
they can be hardwired in a branching program.
Corollary 7.1. Iterated multiplication has branching programs of size
.
Exercise 7.5. Show that given integers
and
one can decide if
in L. You cannot use the fact that iterated multiplication is in L, a result which we stated but not completely proved.
Exercise 7.6. Show that the iterated multiplication of
matrices over the integers has branching programs of size
.
7.2.2 Graphs
We now give another example of the power of L.
Standard time-efficient algorithms to solve this problem mark nodes in the graph. In logarithmic space we can keep track of a constant number of nodes, but it is not clear how we can avoid repeating old steps forever.
Theorem 7.8. [20] Undirected reachability is in L.
The idea behind this result is that a random walk on the graph will visit every node, and can be computed using small space, since we just need to keep track of the current node. Then, one can derandomize the random walk and obtain a deterministic walk, again computable in L.
7.2.3 Linear algebra
Our final example comes from linear algebra. Familiar methods for solving a linear system
can be done requires a lot of space. For example using elimination we need to rewrite the matrix
. Similarly, we cannot easily compute determinants using small space. However, a different method exists.
Theorem 7.9. [9] Solving a linear system is computable in
.
7.3 Checkpoints
The checkpoint technique is a fundamental tool in the study of space-bounded computation. Let us illustrate it at a high level. Let us consider a graph
, and let us write
if there is a path of length
from
to
. The technique allows us to trade the length of the path with quantifiers. Specifically, for any parameter
, we can break down paths from
to
in
smaller paths that go through
checkpoints. The length of the smaller paths needs be only
(assuming that
divides
). We can guess the breakpoints and verify each smaller path separately, at the price of introducing quantifiers but with the gain that the path length got reduced from
to
. The checkpoint technique is thus an instantiation of the general paradigm of guessing computation and verifying it locally, introduced in Chapter 5. One difference is that now we are only going to guess parts of the computation.
The checkpoint technique 
where we denote

and

.
An important aspect of this technique is that it can be applied recursively: We can apply it again to the problems
. We need to introduce more quantifiers, but we can reduce the path length to
, and so on. We will see several instantiations of this technique, for various settings of parameters, ranging from
to
.
We now utilize the checkpoint technique to show a simulation of small-space computation by small-depth alternating circuits.
To illustrate the parameters, suppose
, and let us pick
where
. Then we have circuits of depth
and size
. In other words, we can have depth
and size
, for every
. This in particular holds for every function in
. We will later give explicit functions (also in
) which cannot be computed by circuits of depth
and size
, “just short” of ruling out
. This state of affairs is worth emphasis:
(1) Every

in

has alternating circuits of depth

and size

. (2) We can prove that there are explicit functions (also in L) which cannot be computed by circuits of depth

and size

. (3) Improving the constant in the double exponent for a function in P would yield

. In this sense, the result in (2) is the best possible short of proving a major separation.
The following is a uniform version of Theorem 7.10, and the proof is similar. It shows that we can speed up space-bounded computation with alternations.
Theorem 7.11. [17]Any
is also in
, for any
.
We note that by the generic simulation of alternating time by small-depth circuits in Lemma 6.2, the above theorem also gives a result similar to Theorem 7.10.
7.4 Reductions: L vs. P
Again, we can use reductions to related the space complexity of problems. In particular we can identify the problems in P which have space-efficient algorithms iff every problem in P does.
Definition 7.6. A problem
is P-complete if
and
.
Definition 7.7. The circuit value problem: Given a circuit
and an input
, compute
.
Theorem 7.12. Circuit value is P-complete.
Definition 7.8. The monotone circuit value problem: Given a circuit
with no negations and an input
, compute
.
Exercise 7.7. Prove that monotone circuit value is P-complete.
Recall from section 7.2.3 that finding solutions to linear systems
has space-efficient algorithms. Interestingly, if we generalize equalities to inequalities the problem becomes P complete. This set of results illustrates a sense in which “linear algebra” is easier than “optimization.”
Theorem 7.13. Linear inequalities is P-complete.
7.4.1 Nondeterministic space
Because of the insight we gained from considering non-deterministic time-bounded computation in section º5.1, we are naturally interested in non-deterministic space-bounded computation. In fact, perhaps we will gain even more insight, because this notion will really challenge our understanding of computation.
For starters, let us define non-deterministic space-bounded computation. A naive approach is to define it using the quantifiers from section º6.4, leading to the class
. This is an ill-fated choice:
Exercise 7.8. Prove
.
Instead, non-deterministic space is defined in terms of non-deterministic TMs.
Definition 7.10. A function
is computable in
if there is a two-tape TM which on input
never writes on the first tape and never uses more than
cells on the second, and moreover:
1. The machine is equipped with a special “Guess” state. Upon entering this state, a guess bit is written on the work tape under the head.
2.
iff there exists a choice for the guess bits that causes the machine to output
.
We define
How can we exploit this non-determinism? Recall from section 7.2.2 that reachability in undirected graphs is in L. It is unknown if the same holds for directed graphs. However, we can solve it in NL.
Theorem 7.14. Directed reachability 
Proof. The proof simply amounts to guessing a path in the graph. The algorithm is as follows:
“On input
, let
.
For
to
:
If
, accept.
Guess a neighbor
of
. Let
.
If you haven’t accepted, reject.”
The space needed is
. QED
We can define NL completeness similarly to NP and P completeness, and have the following result.
Theorem 7.15. Directed reachability is NL-complete. That is, it is in NL and it is in L iff
.
Exercise 7.9. Prove this.
7.4.2 Nspace vs. time
Recall by definition
. We showed
in Theorem 7.1. We can strengthen the inclusion to show that it holds even for non-deterministic space.
Theorem 7.16.
.
The next theorem shows that non-deterministic space is not much more powerful than deterministic space: it buys at most a square. Contrast this with the P vs. NP question! The best determistic simulation of NP that we know is the trivial
. Thus the situation for space is entirely different.
How can this be possible? The high-level idea, which was used already in Lemma 7.1, can be cast as follows:
Unlike time, space can be reused.
Theorem 7.17. [23]
, for every
. In particular,
.
Recall that we do not know if
is closed under complement. It is generally believed not to be the case, and we showed that if it is then the PH collapses Exercise 6.3.
What about space? Is
closed under complement? Theorem 7.17 shows
. So if
then the complement function
is in
(and in particular in
). Hence, up to a quadratic loss in space, non-deterministic space is closed under complement.
Can we avoid squaring the space?
Yes! This is weird!
Theorem 7.18. The complement of Path is in NL.
Proof. We want a non-deterministic 2TM that given
accepts if there is no path from
to
in
.
For starters, suppose the machine has computed the number
of nodes reachable from
. The key idea is that there is no path from
to
iff there are
nodes different from
reachable from
. Thus, knowing
we can solve the problem as follows
Algorithm for deciding if there is no path from

to

, given

:


If
Accept, else Reject.
There remains to compute
.
Let
be the nodes at distance
from
, and let
. Note
. We seek to compute
.
To compute
from
, enumerate nodes
(candidate in
). For each
, enumerate over all nodes
in
, and check if
is an edge. If so, increase
by
.
The enumeration over
is done guessing
nodes and paths from
. If we don’t find
nodes, we reject. QED
7.5 TiSp
So far in this chapter we have focused on bounding the space usage. For this, the TM model was sufficient, as remarked at the beginning. It is natural to consider algorithms that operate in little time and space. For this, of course, whether we use TMs or RAMs makes a difference.
Exercise 7.10. Prove
.
An alternative definition of TiSp would allow the RAM to access
cells anywhere in memory. One can maintain a data structure to show that this alternative definition is equivalent to Definition 7.12.
To illustrate the relationship between TiSp, Time, and Space, consider undirected reachability. It is solvable in Time
by bradth-first search, and in logarithmic space by Theorem 7.8. But it isn’t known if it is in
for some constant
.
The following is a non-uniform version of TiSp.
Thus
represents the time of the computation, and
the space.
Recall that Theorem 7.10 gives bounds of the form
on the size of branching program (without distinguishing between length and width). For branching programd og length
and width
this bound gives
. But it gives nothing for power width like
. The state-of-the-art for power width is
[2, 7] (in fact the bound holds even for subexponential) .
With these definitions in hand we can refine the connection between branching programs and small-depth circuits in Theorem 7.10 for circuits of depth 3.
We will later show explicit functions that require depth-3 circuits of size
. Theorem 7.19 shows that improving this would also improve results for small-width branching programs, a refinement of the message emphasized before after Theorem 7.10.
Exercise 7.12. Prove this.
7.6 Notes
For a discussion of the complexity of division, see [3]. For a compendium of P-complete problems see [11].
References
[1] Mikl≤s Ajtai.
-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983.
[2] Mikl≤s Ajtai. A non-linear time lower bound for boolean branching programs. Theory of Computing, 1(1):149–176, 2005.
[3] Eric Allender. The division breakthroughs. Bulletin of the EATCS, 74:61–77, 2001.
[4] Noga Alon, Oded Goldreich, Johan Hσstad, and RenΘ Peralta. Simple constructions of almost
-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.
[5] Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, volume 32, pages 307–314, 1968.
[6] Paul Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM J. Comput., 15(4):994–1003, 1986.
[7] Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. of the ACM, 50(2):154–195, 2003.
[8] Stephen A. Cook. A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences, 7(4):343–353, 1973.
[9] L. Csanky. Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623, 1976.
[10] Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199–214, 1981.
[11] Raymond Greenlaw, H. James Hoover, and Walter Ruzzo. Limits to Parallel Computation: P-Completeness Theory. 02 2001.
[12] John E. Hopcroft, Wolfgang J. Paul, and Leslie G. Valiant. On time versus space. J. ACM, 24(2):332–337, 1977.
[13] Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L’Enseignement MathΘmatique. Revue Internationale. IIe SΘrie, 28(3-4):191–209, 1982.
[14] Leonid A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115–116, 1973.
[15] Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. on Computing, 22(4):838–856, 1993.
[16] E. I. Nechiporuk. A boolean function. Soviet Mathematics-Doklady, 169(4):765–766, 1966.
[17] Valery A. Nepomnjaščiĭ. Rudimentary predicates and Turing calculations. Soviet Mathematics-Doklady, 11(6):1462–1465, 1970.
[18] NEU. From RAM to SAT. Available at http://www.ccs.neu.edu/home/viola/, 2012.
[19] Wolfgang J. Paul, Nicholas Pippenger, Endre SzemerΘdi, and William T. Trotter. On determinism versus non-determinism and related problems (preliminary version). In IEEE Symp. on Foundations of Computer Science (FOCS), pages 429–438, 1983.
[20] Omer Reingold. Undirected connectivity in log-space. J. of the ACM, 55(4), 2008.
[21] J. M. Robson. N by N checkers is exptime complete. SIAM J. Comput., 13(2):252–267, 1984.
[22] Rahul Santhanam. On separators, segregators and time versus space. In IEEE Conf. on Computational Complexity (CCC), pages 286–294, 2001.
[23] Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970.
[24] Michael Sipser. A complexity theoretic approach to randomness. In ACM Symp. on the Theory of Computing (STOC), pages 330–335, 1983.
[25] Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. on Computing, 20(5):865–877, 1991.
[26] Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986.
[27] N. V. Vinodchandran. A note on the circuit complexity of PP. Theor. Comput. Sci., 347(1-2):415–418, 2005.
[28] Emanuele Viola. On approximate majority and probabilistic time. Computational Complexity, 18(3):337–375, 2009.