TCS: Space Complexity

Space Complexity

Space Can Be Reused

Time counts all executed steps; space counts the maximum amount of working memory used at once. An algorithm can revisit the same memory many times

For sublinear space bounds, use a read-only input tape whose cells are excluded from the workspace count. The work tapes are read/write, and their visited cells determine the space cost

SAT is in PSPACE: enumerate assignments with a binary counter and evaluate the formula for each assignment, reusing the same workspace. The running time may be exponential while the space remains polynomial

Configuration Graphs

A configuration contains the state, head positions, and work-tape contents. For $s(n)\ge\log n$, an $O(s(n))$-space machine has at most

$$N=2^{O(s(n))}$$

possible configurations on a fixed input. This count includes the input-head position, which costs $O(\log n)$ bits

A deterministic decider cannot repeat a configuration, since a repetition would cause an infinite loop. Hence

$$\operatorname{SPACE}(s(n)) \subseteq\operatorname{TIME}(2^{O(s(n))})$$

A computation of $t(n)$ steps can visit only $O(t(n))$ work cells, so time also gives a space upper bound. Enumerating polynomial-length NP witnesses yields

$$\mathrm P\subseteq\mathrm{NP}\subseteq \mathrm{PSPACE}\subseteq\mathrm{EXP}$$

Deterministic space is closed under complement by exchanging the answers of a decider. Thus $\mathrm{coNP}\subseteq\mathrm{PSPACE}$ as well

TQBF and PSPACE-Completeness

A fully quantified Boolean formula has no free variables, for example

$$\forall x\ \exists y:\ (x\leftrightarrow y)$$

This formula is true, since $y$ can be chosen after observing $x$. Reversing the quantifiers gives a false formula: one fixed $y$ cannot equal both possible values of $x$

TQBF is the language of true fully quantified Boolean formulas

Membership in PSPACE

Evaluate the quantifiers recursively. At an existential quantifier, OR the results for the two assignments; at a universal quantifier, AND them

Depth-first evaluation stores the current partial assignment, the position in the formula, and a recursion stack of polynomial depth. It reuses space between branches, giving a polynomial-space algorithm

A Succinct Reachability Formula

Let a machine use $s=\operatorname{poly}(n)$ space. Its configurations have $O(s)$ bits and its configuration graph has $2^{O(s)}$ vertices

Write $R_k(c,d)$ for reachability from $c$ to $d$ in at most $2^k$ steps. The natural recurrence is

$$R_k(c,d)=\exists m: R_{k-1}(c,m)\land R_{k-1}(m,d)$$

Expanding both recursive calls would double the formula size at every level. Quantifiers allow the two checks to share one recursive copy

For $b=0$, the recursive call must check the first half; for $b=1$, it must check the second. The midpoint $m$ is chosen before $b$, so both checks use the same midpoint

The base case $R_0$ tests equality or one legal transition. Each level adds $O(s)$ symbols, and $k=O(s)$ levels cover every possible simple configuration path. The resulting formula has polynomial size

Arrange the simulated decider to have a unique canonical accepting configuration. Connecting its start configuration to that accepting configuration gives a polynomial-time reduction to TQBF

Savitch’s Theorem

The midpoint recurrence is also an algorithm. Instead of guessing a midpoint, deterministically enumerate all possible midpoint configurations

To test a path of length at most $2^k$, enumerate $m$ and recursively check the two halves. Accept if some midpoint makes both checks succeed

Each stack frame holds a constant number of configurations and counters, requiring $O(s(n))$ bits. The recursion depth is

$$k=O(\log N)=O(s(n))$$

Thus the total space is $O(s(n)^2)$. Recomputing subproblems may take substantial time, but no exponential table of visited configurations is retained

The polynomial-space consequence is

$$\mathrm{NPSPACE}=\mathrm{PSPACE}$$

This also justifies the oracle equality from Lecture 8: with a TQBF oracle, deterministic and nondeterministic polynomial-time machines have equal power

Games and Alternating Choices

A quantified formula describes a game. The existential player chooses values for existential variables, the universal player chooses values for universal variables, and moves follow the quantifier order

The existential player wins when the final Boolean formula is true. A winning strategy may depend on earlier moves, matching the dependencies allowed by the quantifiers

Deciding the winner is therefore PSPACE-complete. A depth-first minimax traversal uses polynomial space even when its game tree has exponentially many leaves

Generalized Geography

In directed vertex geography, a token starts at a specified vertex. Players alternately move it along an outgoing edge to a vertex not visited earlier; a player with no legal move loses

A play uses at most $|V|$ vertices. Storing the visited set and a depth-first game-search stack uses polynomial space

The problem is PSPACE-hard through a reduction from the quantified-formula game. Variable gadgets encode choices and their move order; a final clause-selection phase lets one player challenge satisfaction and the other exhibit a true literal

The gadget construction must preserve whose turn it is at each interface. Merely having an exponentially large game tree does not establish PSPACE-hardness

L, NL and Small Workspace

A constant number of input positions and counters fit in logarithmic space. For example, palindrome testing can compare symmetric input positions using two counters and a repeatedly scanned read-only input

Directed reachability, PATH, belongs to NL. Store the current vertex, guess a next vertex, verify the edge, and count at most $|V|-1$ moves. If a path exists, a simple path of that length exists

A logarithmic-space machine has only polynomially many configurations. Deterministic graph search on its configuration graph therefore shows

$$\mathrm L\subseteq\mathrm{NL}\subseteq\mathrm P \qquad \mathrm{NL}\subseteq\operatorname{SPACE}(\log^2 n)$$

The second containment is Savitch’s theorem

Log-Space Reductions and NL-Completeness

A log-space transducer has a read-only input, $O(\log n)$ work cells, and a write-only output. The output is not counted as workspace

Write $A\le_L B$ when such a transducer computes a many-one reduction. Polynomial-time reductions would be too powerful here: every language in $\mathrm P$ can be decided during the reduction itself

Composing Small-Space Computations

If the reduction output is polynomially long, it cannot all be stored on a logarithmic work tape. Instead, keep the simulated input-head position of the target algorithm and recompute the required output symbol whenever it is needed

Restarting the transducer costs time, but uses only logarithmic space. This proves closure under composition and the implication $A\le_L B$, $B\in\mathrm L\Rightarrow A\in\mathrm L$

PATH Is NL-Complete

For any NL machine, map an input to its configuration graph with distinguished start and accepting vertices. An accepting computation exists exactly when those vertices are connected by a directed path

Two configuration descriptions occupy only $O(\log n)$ bits. A transducer can enumerate configuration pairs, test whether a legal transition joins them, and output graph edges one at a time

Thus every NL language log-space reduces to PATH

Complementation and Hierarchy

The proof certifies the number of reachable vertices by inductive counting. It does not complement a nondeterministic machine simply by swapping its accepting and rejecting states. The counting argument is developed at the beginning of Lecture A

For space-constructible $s_1,s_2\ge\log n$ with $s_1(n)=o(s_2(n))$, the deterministic space hierarchy gives

$$\operatorname{SPACE}(s_1(n)) \subsetneq\operatorname{SPACE}(s_2(n))$$

Combining this with Savitch’s bound shows $\mathrm{NL}\subsetneq\mathrm{PSPACE}$. The individual equalities $\mathrm L=\mathrm{NL}$, $\mathrm{NL}=\mathrm P$, and $\mathrm P=\mathrm{NP}$ are not settled by these hierarchy arguments