Space Complexity

And the third row is chapter 61's, where the machine's space is the input's length and the languages are exactly the context sensitive ones.

The two results that differ from time's

Space is more powerful than time, cell for cell

Any machine running in time T uses at most T cells, as above. But a machine using S cells may run for far longer than S steps, because it may revisit them.

How long can it run? Chapter 61 counted it. With q states, a tape alphabet of size g and S cells there are q times S times g to the S configurations, and a halting machine cannot repeat one, so:

So space S buys time exponential in S, and that is why PSPACE contains P and is believed to be much larger.

Nondeterminism costs much less for space than for time

This is the striking one, and the contrast with chapter 69 is the point.

For time, removing nondeterminism costs an exponential, as chapter 69 showed, and whether that can be improved is open.

For space, it costs only a square. That is Savitch's theorem: a nondeterministic machine using space S can be simulated by a deterministic one using space about S squared. So

Why the difference. A deterministic simulation of a nondeterministic machine has to explore a tree. For time that means visiting every branch, and there are exponentially many. For space it does not: the branches can be explored one at a time and the same cells reused for each, so only the depth of the recursion is paid for. The asymmetry at the top of this chapter is doing all the work.

And the consequence, from chapter 61. Nondeterministic linear space equals the context sensitive languages, and by Savitch it sits inside deterministic space n squared. Whether it equals deterministic LINEAR space is the open question chapter 60 recorded from Immerman's own paper.

And nondeterministic space is closed under complement

Chapter 61 gave this as Immerman's 1988 result. It is worth seeing here in its general form, because it is the other place where space behaves better than time: nondeterministic space is closed under complementation for any bound at least logarithmic, while whether nondeterministic TIME is closed under complement is not known and is one of the standard open questions.

Three results, all in space's favour, and all traceable to reuse.

Measured examples

Both columns below were measured by running the machines, not estimated.

Read the last three rows. The doubling machine's space grows linearly, 4 then 6 then 8, two cells per extra input symbol, while its time grows quadratically, 10 then 24 then 44. The same machine is cheap in space and expensive in time, which is the asymmetry made visible, and it is expensive in time precisely because it keeps going back over the cells it already has.

The picture, with both measures

Every containment in that table is known, and almost none of them is known to be strict. The one that is, and it is the only one this syllabus needs, is that P is properly inside EXPTIME, by the hierarchy theorem of chapter 86.

Distinctions

What it does NOT mean

Space is not memory in bytes. It is tape cells, and the cells hold symbols from a fixed finite alphabet.

Small space does not mean fast. The doubling machine uses 8 cells and 44 moves, and a machine using S cells may run for exponentially many steps in S.

Savitch's theorem does not say nondeterminism is free for space. It says it costs a square, which for a polynomial bound is still a polynomial and for a linear bound is not linear, which is why chapter 60's question is open.

Logarithmic space is not nothing. It is enough to hold a position in the input, which is enough for a great many algorithms.

The offline machine is not a different model. Chapter 69 showed it is the ordinary machine with the input tape made read only, which costs nothing.

Quick revision

• S(n) is the maximum number of tape cells visited on any input of length n, for a machine that halts on every

input.

• Space can be reused and time cannot, and every difference between the two measures follows from that.
• Space is at most time, always. Time is at most about g to the S for space S, by counting configurations.
• Sublinear space needs the offline machine, whose read only input tape is not counted; that is why it exists.
• Logarithmic space holds a position in the input but not a copy of it.
• Removing nondeterminism costs an exponential in time and only a SQUARE in space, by Savitch's theorem, because

the branches of the tree can reuse the same cells.

• Nondeterministic space is closed under complement, by Immerman 1988; the corresponding question for time is

open.

• L inside NL inside P inside NP inside PSPACE inside EXPTIME, with only the outer pair known to be strict.

Test yourself

1. Define space complexity, and say why the offline machine is needed. The maximum number of tape cells visited on any input of length n. The offline machine is needed for sublinear bounds, because on an ordinary machine the input itself occupies n cells and no machine could use fewer.

2. Give the inequality between space and time, in both directions. Space is at most time, since reaching a new cell costs a move. Time is at most about g to the S for space S, since a halting machine cannot repeat a configuration and there are that many.

3. State Savitch's theorem and explain why space is cheaper than time here. A nondeterministic machine using space S can be simulated deterministically in space about S squared. It is cheaper because the branches of the computation tree can be explored one at a time reusing the same cells, while in time each branch must be paid for separately.

4. The doubling machine uses 6 cells and 24 moves on one input and 8 cells and 44 on the next. What does that show? That space and time can grow at different rates for the same machine: the space is linear and the time quadratic, because the machine keeps revisiting cells it already has.

5. What does logarithmic space suffice for, and what not? It suffices to hold a position or a counter in the input, since a number up to n needs about log n digits. It does not suffice to hold a copy of the input.

6. Name two ways in which nondeterminism behaves better for space than for time. Removing it costs only a square rather than an exponential, by Savitch; and nondeterministic space is known to be closed under complement, while the corresponding question for nondeterministic time is open.