47.02.06 · theoretical-cs / 02-complexity-fundamentals

L, NL, and the Immerman-Szelepcsenyi Theorem

shipped3 tiersLean: none

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §4.3 (NL, coNL, the inductive counting argument of Immerman-Szelepcsenyi with full proof, the consequences for the low levels of the space hierarchy, and connections to circuit complexity); Sipser 2013 §8.4; Papadimitriou 1994 Computational Complexity (Addison-Wesley) Ch. 7

Intuition Beginner

Imagine you are a robot walking through a city, trying to get from your hotel to the museum. You have no map, and you can only remember a constant number of street names at any time. Can you navigate? The answer depends on whether you are allowed to make lucky guesses.

If you must plan deterministically, with only a fixed-size memory, you are limited to the class L — problems solvable in logarithmic space. Logarithmic space means you can remember only a handful of numbers about the size of the input, not the input itself. Remarkably, some useful problems still fit in this budget.

If you are allowed to make nondeterministic guesses — "try this street, and if it works, great" — you enter the class NL. The gap between L and NL is the space analogue of the gap between P and NP, but it lives at a much tighter scale.

The biggest surprise in this area is that NL is closed under complement. If a problem can be solved with nondeterministic log-space guesses, then its negation can too. This is nothing like the NP situation, where whether NP equals coNP is a major open question. For logarithmic space, nondeterminism is weak enough that we can prove it adds no power when you flip the answer.

Visual Beginner

The space complexity hierarchy at the logarithmic level and its relationship to the polynomial levels.

       PSPACE
      /      \
   P  -----  NP
   |         |
   L  -----  NL

The key relationships. L sits inside NL, just as P sits inside NP. But unlike the P-vs-NP question, we know NL = coNL (Immerman-Szelepcsenyi, 1987). The inclusion NL within P follows from the fact that a log-space nondeterministic machine has at most polynomially many configurations.

class	resource	deterministic version
L	$SPACE (lo g n)$	itself
NL	$NSPACE (lo g n)$	inside $SPACE (lo g^{2} n)$ by Savitch
P	$TIME (n^{k})$	itself
NP	$NTIME (n^{k})$	unknown

Worked example Beginner

Take the PATH problem: given a directed graph $G$ with nodes $s$ and $t$ , does a directed path from $s$ to $t$ exist? This is the canonical NL-complete problem.

A nondeterministic log-space algorithm works as follows. Start at $s$ . At each step, nondeterministically pick an outgoing edge and follow it. Store only the current node number, which takes $O (lo g n)$ bits for a graph with $n$ nodes. After at most $n$ steps (since any simple path has at most $n$ nodes), either you reach $t$ and accept, or you give up and reject.

If a path exists, some sequence of lucky guesses follows it, so the machine accepts. If no path exists, no guessing sequence can reach $t$ , so the machine always rejects. This shows PATH is in NL.

The harder direction is that every NL problem reduces to PATH. The idea is that any nondeterministic log-space computation on input $x$ has a configuration graph with polynomially many vertices, and the machine accepts if and only if there is a path from the start configuration to an accepting one. Since the configuration graph can be constructed on-the-fly in log space, this gives a log-space reduction.

Check your understanding Beginner

Formal definition Intermediate+

For a function $f : N \to N$ , define $SPACE (f (n))$ and $NSPACE (f (n))$ as in 47.02.05. The logarithmic-space classes are

L = SPACE (lo g n), NL = NSPACE (lo g n) .

Equivalently, $L$ is the class of languages decidable by a deterministic Turing machine that uses $O (lo g n)$ cells on its work tape (the read-only input tape is not counted), and $NL$ is the nondeterministic variant.

A log-space reduction from $A$ to $B$ is a function $f$ computable in $O (lo g n)$ space such that $x \in A ⟺ f (x) \in B$ . A language $B$ is NL-complete if $B \in NL$ and every $A \in NL$ log-space reduces to $B$ .

The language

PATH = {⟨ G, s, t ⟩ : G is a directed graph with a path from s to t}

is the canonical NL-complete problem. Its complement $\overline{PATH} = {⟨ G, s, t ⟩ : no path from s to t in G}$ is $coNL$ -complete.

The key structural facts are: $L \subseteq NL \subseteq P$ , $NL \subseteq SPACE (lo g^{2} n)$ by Savitch's theorem 47.02.05, and $NL = coNL$ by the Immerman-Szelepcsenyi theorem. Whether $L = NL$ remains open ^{[Arora-Barak §4.3]}.

Counterexamples to common slips Intermediate+

"NL = coNL implies L = NL." It does not. Closure under complement says that the complement of every NL language is also in NL. This does not collapse NL to its deterministic version. The relationship between L and NL is analogous to P versus NP — closure under complement is a weaker statement than derandomisation of nondeterminism.
"Savitch gives the best known simulation of NL in deterministic space." This is correct: $NL \subseteq SPACE (lo g^{2} n)$ is the best known upper bound. Whether $NL \subseteq SPACE (lo g n) = L$ is a major open question. No improvement on Savitch's bound is known even for the specific case of graph reachability.
"PATH is NL-complete, so it cannot be in L." NL-completeness means PATH is among the hardest problems in NL, but we do not know whether L = NL. If L = NL, then PATH would be in L. The completeness result only tells us that PATH is in L if and only if every NL problem is in L.

Key theorem with proof Intermediate+

Theorem (Immerman-Szelepcsenyi). For space-constructible $f (n) \geq lo g n$ , $NSPACE (f (n)) = coNSPACE (f (n))$ . In particular, $NL = coNL$ .

Proof. The proof uses an inductive counting technique. We show $\overline{PATH} \in NL$ , which suffices since $\overline{PATH}$ is $coNL$ -complete.

Let $G$ be a graph on $n$ vertices. For a vertex $s$ and integer $k \geq 0$ , define $R_{k} (s) = {v : v is reachable from s in at most k steps}$ and $c_{k} = ∣ R_{k} (s) ∣$ . Note $c_{0} = 1$ (only $s$ itself). The goal is to decide, given $s, t$ , whether $t \in / R_{n - 1} (s)$ .

Inductive step: Suppose an NL machine knows $c_{k}$ . It can compute $c_{k + 1}$ in NL as follows. Initialize a counter $d = 0$ . For each vertex $u$ (loop over all $n$ vertices): nondeterministically verify that $u \in R_{k} (s)$ by guessing a path of length $\leq k$ from $s$ to $u$ . If verification succeeds, check if any neighbour of $u$ is the current vertex $v$ . If so, $v$ is reachable in $k + 1$ steps.

To compute $c_{k + 1}$ : iterate over all vertices $v$ . For each $v$ , use the above procedure to check membership in $R_{k + 1} (s)$ . But there is a subtlety: the nondeterministic verification might reject a reachable vertex. The fix is to use the count $c_{k}$ as a certificate of completeness: after scanning all $u$ , if we have found exactly $c_{k}$ vertices in $R_{k} (s)$ , then we know we have found all of them. This ensures no reachable vertex is missed.

Starting from $c_{0} = 1$ , compute $c_{1}, c_{2}, \dots, c_{n - 1}$ inductively. After computing $c_{n - 1}$ , we know exactly how many vertices are reachable from $s$ . Now check whether $t$ is among them: guess paths to $c_{n - 1}$ distinct vertices, and if none equals $t$ , then $t$ is unreachable — accept. If $t$ is found among them, reject.

The machine uses $O (lo g n)$ space: it stores counters $k, d, c_{k}, c_{k + 1}$ (each $O (lo g n)$ bits), the current vertex (also $O (lo g n)$ ), and the nondeterministic path guesses reuse the same space. $□$

Bridge. This theorem is the foundational reason the space complexity landscape is more tractable at the logarithmic level than the time complexity landscape at the polynomial level: nondeterminism in log space is so constrained that even its complement fits within the same class, and this is exactly the kind of structural collapse that has no known time analogue (NP versus coNP remains wide open). The inductive counting technique builds toward the circuit complexity results in 47.03.02 where similar counting arguments appear, and it appears again in the derandomisation programme 47.05.05 where explicit constructions of pseudorandom generators for space-bounded computation rely on counting reachability sets. The central insight is that knowing $∣ R_{k} ∣$ certifies completeness of a nondeterministic search — putting these together, the inductive chain $c_{0} \to c_{1} \to \dots \to c_{n - 1}$ turns a "there exists" question into a sequence of verified counts, and the bridge is that this counting trick works in NL precisely because log-space machines can count to polynomial quantities while storing only logarithmically many bits.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that the language $2SAT = {ϕ : ϕ is a satisfiable 2-CNF formula}$ is in NL.

Hint

Reduce 2SAT to graph reachability. Build an implication graph and check for contradictory cycles.

Answer

For a 2-CNF clause $(x \lor y)$ , create implications $\neg x \to y$ and $\neg y \to x$ in an implication graph on $2 n$ vertices (one for each literal). The formula is unsatisfiable iff there exists a variable $x$ such that $x$ implies $\neg x$ and $\neg x$ implies $x$ — i.e., there are paths from $x$ to $\neg x$ and from $\neg x$ to $x$ . Since PATH is in NL, checking each pair $(x, \neg x)$ for mutual reachability is in NL: nondeterministically test whether no variable has both implications. Hence $\overline{2SAT} \in NL$ , and by NL = coNL, $2 SAT \in NL$ . Rubric: full credit for the implication graph construction and the PATH reduction.

Exercise 4 (medium, symbolic).

Prove that log-space reductions are transitive: if $A \leq_{L} B$ and $B \leq_{L} C$ , then $A \leq_{L} C$ .

Hint

Compose the two reductions. The challenge is that the second reduction reads the output of the first, which cannot be stored in log space. Use the trick of recomputing bits of the intermediate output on demand.

Answer

Let $f$ reduce $A$ to $B$ in log space and $g$ reduce $B$ to $C$ in log space. The composed reduction $h (x) = g (f (x))$ cannot write $f (x)$ to a tape (it may be polynomially long). Instead, simulate $g$ on a virtual input tape: whenever $g$ needs the $i$ -th symbol of $f (x)$ , recompute $f (x)$ from scratch up to position $i$ . Recomputing $f (x)$ uses $O (lo g ∣ x ∣)$ space. The simulation stores the position counter $i$ ( $O (lo g n)$ bits) and the work space of both machines ( $O (lo g n)$ each). Total space: $O (lo g n)$ . Hence $h$ is a log-space reduction. Rubric: full credit for the recomputation trick and the space analysis.

Exercise 6 (hard, symbolic).

Give a full proof that the PATH problem is NL-hard: every language $L \in NL$ log-space reduces to PATH.

Hint

Encode the configuration graph of the NL machine. The reduction must be computable in log space, so the graph cannot be explicitly written out.

Answer

Let $M$ be an NL machine deciding $L$ using $c lo g n$ space. A configuration of $M$ on input $x$ consists of the state, input head position ( $O (lo g n)$ bits), and work tape contents and head position ( $O (lo g n)$ bits), totaling $O (lo g n)$ bits — so there are $n^{O (1)}$ distinct configurations. Define $G_{M, x}$ with configurations as vertices and an edge $(C_{1}, C_{2})$ iff $M$ can transition from $C_{1}$ to $C_{2}$ in one step.

The reduction $f$ maps $x$ to $⟨ G_{M, x}, C_{s}, C_{a} ⟩$ where $C_{s}$ is the start configuration and $C_{a}$ is the (unique) accepting configuration. Then $x \in L$ iff there is a path from $C_{s}$ to $C_{a}$ in $G_{M, x}$ .

The graph $G_{M, x}$ is not written explicitly. Instead, the reduction outputs a circuit (or oracle) description that, given two configuration descriptions $C_{1}, C_{2}$ , determines whether $(C_{1}, C_{2})$ is an edge by simulating one step of $M$ . This simulation uses $O (lo g n)$ space. Since log-space reductions can use this on-the-fly construction, $f$ is a log-space reduction. Rubric: full credit for the configuration-graph encoding and the on-the-fly edge computation.

Exercise 7 (hard, symbolic).

Prove that $NL \subseteq NC^{2}$ (the class of problems solvable by polynomial-size, $O (lo g^{2} n)$ -depth circuits). Conclude that NL problems have fast parallel algorithms.

Hint

Use the Savitch recursion to build a circuit. Each recursive call becomes a sub-circuit, and the depth is $O (lo g^{2} n)$ .

Answer

For an NL machine $M$ using $O (lo g n)$ space, the configuration graph has $N = n^{O (1)}$ vertices. Build a circuit for the PATH predicate using the Savitch recursion: $REACH (a, b, t)$ checks reachability in $2^{t}$ steps. The base case $t = 0$ is a single gate (edge check). For $t \geq 1$ : $REACH (a, b, t) = ⋁_{m} (REACH (a, m, t - 1) \land REACH (m, b, t - 1))$ . The OR over all midpoints has $N = n^{O (1)}$ fan-in (realised by a tree of OR gates of depth $O (lo g N) = O (lo g n)$ ). The recursion depth is $T = O (lo g N) = O (lo g n)$ . Total circuit depth: $O (lo g n) \cdot O (lo g n) = O (lo g^{2} n)$ . Circuit size: polynomial, since each level produces $N^{2}$ sub-problems (pairs of endpoints) and there are $O (lo g n)$ levels. Hence $NL \subseteq NC^{2}$ . Rubric: full credit for the circuit construction and the depth/size analysis.

Exercise 8 (hard, symbolic).

The Immerman-Szelepcsenyi theorem generalises: prove that for any space-constructible $f (n) \geq lo g n$ , $NSPACE (f (n)) = coNSPACE (f (n))$ .

Hint

The same inductive counting argument works. The machine uses $O (f (n))$ space to store counters and configurations, and the number of configurations is $2^{O (f (n))}$ .

Answer

Let $M$ be an $NSPACE (f (n))$ machine. Its configuration graph has $N = 2^{O (f (n))}$ vertices. Define $c_{k} = ∣ R_{k} (s) ∣$ as before. The base case $c_{0} = 1$ is computed directly. For the inductive step from $c_{k}$ to $c_{k + 1}$ : iterate over all $N$ vertices $v$ . For each $v$ , nondeterministically verify membership in $R_{k + 1} (s)$ by guessing a path of length $\leq k + 1$ . Use $c_{k}$ as a completeness certificate to ensure no reachable vertex is missed. The machine stores: the current vertex ( $O (f (n))$ bits), counters $c_{k}, c_{k + 1}, d$ (each $O (f (n))$ bits), and the nondeterministic path ( $O (f (n))$ bits). Total space: $O (f (n))$ . After computing $c_{N}$ , check whether $t$ is unreachable. Hence $\overline{L (M)} \in NSPACE (O (f (n))) = NSPACE (f (n))$ , giving $coNSPACE (f (n)) \subseteq NSPACE (f (n))$ . The reverse inclusion is by symmetry. Rubric: full credit for generalising the counting argument and verifying the space bound.

Advanced results Master

The Immerman-Szelepcsenyi theorem opened the door to a detailed understanding of space-bounded computation. The results below explore the consequences and generalisations.

Theorem 1 (NL = coNL, full detail). The proof has two key components: (a) computing $c_{k}$ from $c_{k - 1}$ in NL, and (b) using $c_{n - 1}$ to decide $\overline{PATH}$ . For (a), the machine maintains two counters: $c_{k - 1}$ (given) and $c_{k}$ (being computed). For each vertex $v$ , it determines whether $v \in R_{k} (s)$ by scanning all vertices $u$ and guessing paths of length $k - 1$ from $s$ to $u$ . When a path to $u$ is found, check if $(u, v)$ is an edge. The count $c_{k - 1}$ ensures completeness: after scanning all $u$ , if exactly $c_{k - 1}$ of them were verified as reachable, the scan was exhaustive. For (b), with $c_{n - 1}$ known, guess $c_{n - 1}$ distinct reachable vertices and verify that $t$ is not among them ^{[Arora-Barak §4.3]}.

Theorem 2 (Savitch at the logarithmic level). The bound $NL \subseteq SPACE (lo g^{2} n)$ from Savitch's theorem 47.02.05 is the best known deterministic upper bound for NL. No improvement is known, and the question $NL = ? L$ remains one of the fundamental open problems in complexity theory. The Reingold theorem (2005) showed that undirected graph reachability is in L, giving $SL = L$ , but the directed case remains open.

Theorem 3 (NL and circuit complexity). The inclusion $NL \subseteq NC^{2}$ follows from the Savitch recursion translated into circuits. This places NL problems in the realm of efficient parallel computation. The converse relationship — whether $NC^{1} \subseteq NL$ — involves the complexity of formula evaluation and is related to the question of whether Boolean formula value is complete for $NC^{1}$ ^{[Arora-Barak §6.2]}.

Theorem 4 (downward self-reducibility and NL). Many NL-complete problems exhibit downward self-reducibility: the answer for input size $n$ can be obtained from answers for inputs of size $n - 1$ . For PATH, removing a vertex and asking about reachability in the smaller graph is a form of self-reducibility. This property connects to the randomised algorithms for space-bounded computation in 47.05.01, where random walks on graphs approximate reachability probabilities.

Theorem 5 (space-bounded hierarchies). The space hierarchy theorem gives $L ⊊ SPACE (lo g^{2} n) ⊊ PSPACE$ , so the logarithmic landscape has genuine structure. Whether the intermediate classes form a strict hierarchy depends on unresolved questions. The Immerman-Szelepcsenyi theorem implies that the nondeterministic space hierarchy at the log level has no "gap" at the complement: $NL = coNL$ , $NSPACE (lo g^{2} n) = coNSPACE (lo g^{2} n)$ , and so on ^{[Arora-Barak §4.3]}.

Synthesis. The foundational reason NL = coNL is that nondeterministic log-space machines are constrained enough that their computation graphs can be analysed inductively, and this is exactly the structural property that distinguishes space from time at every level of the hierarchy. The inductive counting technique builds toward the more general result that $NSPACE (f) = coNSPACE (f)$ for all space-constructible $f$ , and it appears again in the derandomisation of space-bounded computation 47.05.05 where explicit constructions for pseudorandom generators rely on counting reachable configurations. The central insight is that a count serves as a compact certificate of exhaustive search — putting these together, knowing $∣ R_{k} ∣$ lets you verify that every reachable vertex has been found, and this certificate propagates through the inductive chain. The bridge is that this self-certifying property of space-bounded nondeterminism generalises to give $NSPACE (f) = coNSPACE (f)$ at every level, which is dual to the collapse $PSPACE = NPSPACE$ from 47.02.05, and the generalises connection from NL to NC circuits shows that space-bounded nondeterminism sits naturally within the parallel computation framework.

Full proof set Master

Proposition 1 (PATH is NL-complete). $PATH \in NL$ and every $L \in NL$ log-space reduces to PATH.

Proof. Membership: a nondeterministic log-space machine starts at $s$ and repeatedly guesses a successor vertex. Store only the current vertex ( $O (lo g n)$ bits) and a step counter ( $O (lo g n)$ bits). If $t$ is reached within $n$ steps, accept.

Hardness: let $M$ decide $L$ in $NL$ . The configuration graph $G_{M, x}$ has $N = n^{O (1)}$ vertices, each described in $O (lo g n)$ bits. The reduction maps $x$ to $(G_{M, x}, C_{s}, C_{a})$ where $C_{s}$ is the start configuration and $C_{a}$ is the accepting configuration. The graph is described implicitly: given two configuration descriptions, the edge relation is computed by simulating one step of $M$ , using $O (lo g n)$ space. Then $x \in L$ iff there is a path from $C_{s}$ to $C_{a}$ in $G_{M, x}$ . $□$

Proposition 2 (Immerman-Szelepcsenyi). $NL = coNL$ .

Proof. We show $\overline{PATH} \in NL$ . Let $G$ have vertex set ${0, 1, \dots, n - 1}$ and let $c_{k} = ∣ R_{k} (s) ∣$ . Compute $c_{0} = 1$ . Inductively compute $c_{k}$ from $c_{k - 1}$ : for each vertex $v$ , determine whether $v \in R_{k} (s)$ by scanning all vertices $u$ . For each $u$ , nondeterministically guess a path of length $\leq k - 1$ from $s$ to $u$ . If a path is found and $(u, v)$ is an edge, mark $v$ as reachable. Keep a count of how many $u$ 's were verified. After scanning all $u$ , if the count equals $c_{k - 1}$ , the search was complete (every reachable $u$ was found). Increment $c_{k}$ if $v$ was marked. This uses $O (lo g n)$ space for counters and vertex labels.

After $n - 1$ rounds, $c_{n - 1}$ is known. To decide whether $t \in / R_{n - 1} (s)$ : nondeterministically guess paths to $c_{n - 1}$ distinct vertices. If $t$ is not among them and exactly $c_{n - 1}$ vertices are found, accept ( $t$ is unreachable). Otherwise reject. $□$

Proposition 3 (NL within P). $NL \subseteq P$ .

Proof. An NL machine $M$ on input $x$ uses $O (lo g n)$ space, giving $N = n^{O (1)}$ configurations. Construct the configuration graph $G_{M, x}$ with $N$ vertices. Reachability in a directed graph with $N$ vertices is decidable in $O (N^{2})$ time by BFS/DFS. The accepting configuration is reachable from the start configuration iff $x \in L (M)$ . Total time: $N^{O (1)} = n^{O (1)}$ , hence $NL \subseteq P$ . $□$

Proposition 4 (generalisation to all space bounds). For space-constructible $f (n) \geq lo g n$ , $NSPACE (f (n)) = coNSPACE (f (n))$ .

Proof. The identical inductive counting argument works. The $NSPACE (f)$ machine has $N = 2^{O (f (n))}$ configurations. The machine stores counters of size $O (f (n))$ bits and vertex labels of $O (f (n))$ bits, using total space $O (f (n))$ . The induction runs for $N$ rounds, each requiring $O (f (n))$ space. $□$

Connections Master

Space complexity and PSPACE 47.02.05 provides the framework that this unit specialises to the logarithmic level. Savitch's theorem gives $NL \subseteq SPACE (lo g^{2} n)$ , and the Immerman-Szelepcsenyi theorem complements this by showing that nondeterministic and co-nondeterministic log space coincide.
Time complexity P and NP 47.02.01 is the polynomial-time analogue of this unit's topic. The relationship $L \subseteq NL$ mirrors $P \subseteq NP$ , but the Immerman-Szelepcsenyi theorem shows that NL = coNL, whereas NP versus coNP remains open.
Interactive proofs 47.03.04 use the counting technique from this unit in the arithmetisation of quantifier predicates. The NL = coNL proof is a miniature version of the IP = PSPACE argument, where counting certifiable sets replaces probabilistic verification.
Circuit complexity 47.03.02 connects to NL through the inclusion $NL \subseteq NC^{2}$ , which translates the Savitch recursion into a bounded-depth circuit family.

Historical & philosophical context Master

The Immerman-Szelepcsenyi theorem was proved independently by Neil Immerman and R ostislav Szelepcsenyi in 1987, resolving a question that had been open since the early 1970s. Immerman's paper, "Nondeterministic Space is Closed Under Complementation" (1988), and Szelepcsenyi's paper, "The Method of Forced Estimation for Proving Nondeterministic Space is Closed Under Complementation" (1988), both appeared in the SIAM Journal on Computing. The result was surprising because the analogous question for time (NP versus coNP) remains wide open, and most researchers had expected the space version to be equally hard ^{[Arora-Barak §4.3]}.

The technique of inductive counting introduced in these proofs has become a standard tool in complexity theory. It demonstrates that counting and verification can be interleaved in a way that preserves space bounds, a principle that reappears in the IP = PSPACE proof and in the theory of pseudorandom generators for space-bounded computation.

The Reingold theorem of 2005, showing that undirected graph reachability is in L (and hence $SL = L$ ), extended the structural understanding of space-bounded classes. Directed reachability remains in NL but not known to be in L, making it the canonical candidate for separating L from NL.

Bibliography Master

@article{immerman1988nondeterministic,
  author  = {Immerman, Neil},
  title   = {Nondeterministic space is closed under complementation},
  journal = {SIAM Journal on Computing},
  volume  = {17},
  number  = {5},
  year    = {1988},
  pages   = {935--938}
}

@article{szelepcsenyi1988method,
  author  = {Szelepcsenyi, Rostislav},
  title   = {The method of forced estimation for proving nondeterministic space is closed under complementation},
  journal = {Slovo a Slovesnost},
  year    = {1988}
}

@article{reingold2005undirected,
  author  = {Reingold, Omer},
  title   = {Undirected connectivity in log-space},
  journal = {Journal of the ACM},
  volume  = {55},
  number  = {4},
  year    = {2008},
  pages   = {1--24}
}

@book{sipser2013introduction,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  publisher = {Cengage Learning},
  edition   = {3rd},
  year      = {2013}
}

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009}
}

@book{papadimitriou1994computational,
  author    = {Papadimitriou, Christos H.},
  title     = {Computational Complexity},
  publisher = {Addison-Wesley},
  year      = {1994}
}

Prerequisites

47.02.05

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §8.4 (logarithmic space as a very tight memory bound, the classes L and NL, and why NL is the natural space analogue of NP)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §8.4 (L, NL, NL-completeness, PATH as the canonical NL-complete problem, and the Immerman-Szelepcsenyi theorem that NL = coNL); Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §4.3
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §4.3 (NL, coNL, the inductive counting argument of Immerman-Szelepcsenyi with full proof, the consequences for the low levels of the space hierarchy, and connections to circuit complexity); Sipser 2013 §8.4; Papadimitriou 1994 Computational Complexity (Addison-Wesley) Ch. 7

References

Sipser, M. — Introduction to the Theory of Computation · Cengage, 3rd edition (2013). §8.4 defines logarithmic space: $L = SPACE (lo g n)$ and $NL = NSPACE (lo g n)$ , observes that $L \subseteq NL \subseteq P$ (a log-space machine has polynomially many configurations and hence runs in polynomial time if it halts), defines NL-completeness under log-space reductions, proves that $PATH = {⟨ G, s, t ⟩ : G has a directed path from s to t}$ is NL-complete via a log-space encoding of the configuration graph, and states the Immerman-Szelepcsenyi theorem $NL = coNL$ — the complement of PATH, namely $\overline{PATH} = {⟨ G, s, t ⟩ : no path from s to t}$ , is also in NL — with a proof sketch of the inductive counting argument.
Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). §4.3 develops the theory of log-space computation, defines $L$ and $NL$ , proves PATH is NL-complete, gives the full proof of the Immerman-Szelepcsenyi theorem using inductive counting: a log-space nondeterministic machine can count the number of vertices reachable from $s$ within distance $k$ , and using this count it can determine whether $t$ is among the unreachable vertices; §4.3 also discusses $NL \subseteq P$ and $NL \subseteq SPACE (lo g^{2} n)$ by Savitch, and the connection to circuit complexity via $NL \subseteq NC^{2}$ .

Estimated time

beginner: 15m
intermediate: 45m
master: 85m