# NL = co-NL

In 1988, Neil Immerman (now Professor Emeritus at UMass Amherst, as of 2024) published a famous paper in which he proved

I first learned their theorem (now widely known as Immerman-Szelepcsényi) in an undergraduate course that covered, among other topics, introductory complexity theory. We discussed the proof idea only briefly in class as we were more interested in the result itself, but there are a number of interesting results about alternation that follow from the proof. This post discusses the idea behind the Immerman-Szelepcsényi theorem.

## The Basics

I forego restating any formal definitions of a Turing machine for the sake of brevity; any standard formulation (e.g. Sipser or Hopcroft-Ullman) suffices.

Given some function

## Connectivity in NL

We now divert our attention to a particular graph problem that will be of use to us: s-t connectivity. Given a directed graph

There is an obvious argument that places

It turns out that *non-connectivity* problem.

## Non-connectivity in NL

The complement of the s-t connectivity problem asks, given graph *not* exist a path from

Since

It is not immediately obvious how we can decide non-connectivity in nondeterministic log-space. Doing a graph search from

So how did they approach the problem? The idea is quite clever, and there are no advanced mechanisms involved. Given graph

Immerman and Szelepcsényi's key insight is that *it's possible to progressively verify *. It is very easy to check

Suppose

We compute

So we're essentially done! We have described an inductive procedure to certify

## NL = co-NL

We spent a great deal of time talking about graph connectivity problems. How does this help us show

Consider some arbitrary *configuration graph*, i.e. a graph with nodes as configurations of the Turing machine and edges as valid transitions between configurations. We reduce to

It follows that

## Results Related to Alternating Space

From Immerman-Szelepcsényi we can prove that the "log-space hierarchy" collapses to

(－.－)...zzz - Aaron