NL = co-NL

In 1988, Neil Immerman (now Professor Emeritus at UMass Amherst, as of 2024) published a famous paper in which he proved ; in the same year, Róbert Szelepcsényi independently proved the same result.

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 , we let denote the set of all problems decidable by a nondeterministic Turing machine in space. In this post we are particularly interested in the class , which also goes by the name . For context, is known to be a subset of , but it is not known whether the inclusion is strict.

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 and vertices and , we can ask whether there exists a path from to . Formally, let denote the set of all tuples such that is a (directed) graph with a path from to .

There is an obvious argument that places in : supposing has vertices, we nondeterministically guess an walk of at most edges. Instead of writing down the entire walk, we guess vertex-to-vertex, writing down only the current vertex and the total number of edges traversed so far—this can be done in logarithmic space. If an path exists, then there exists a walk from to using at most edges; if no path exists then we clearly cannot find such a walk.

It turns out that is complete for , another simple result. We will return to this later; for now we direct our attention to the s-t non-connectivity problem.

Non-connectivity in NL

The complement of the s-t connectivity problem asks, given graph and vertices and , whether there does not exist a path from to . Formally, let denote the set of all tuples such that does not have an path.

Since is in , we immediately have that is in . As we will soon discover, is also in ; this is precisely the result that Immerman and Szelepcsényi proved.

It is not immediately obvious how we can decide non-connectivity in nondeterministic log-space. Doing a graph search from already requires linear space, and any approach that involves verifying all possible paths from to fails because there are too many possible paths to enumerate in log-space! In fact, the result was surprising enough that Immerman and Szelepcsényi won the 1995 Gödel prize for their work.

So how did they approach the problem? The idea is quite clever, and there are no advanced mechanisms involved. Given graph and vertices and , we focus on subproblems of the form "is reachable from in at most steps?" To this end, it will be beneficial to define sets of the form denoting the sets of all vertices in that are reachable from in at most steps. It is obvious that an equivalent formulation of is to ask whether holds.

Immerman and Szelepcsényi's key insight is that it's possible to progressively verify for from to . It is very easy to check in log-space; we simply check all edges from and verify that none of them point to . Incidentally, we can also compute in log-space by counting the number of outgoing edges from . How does this help us? It turns out that knowing allows us to nondeterministically (a) verify and (b) compute .

Suppose is known. To verify , it suffices to check that for every vertex there is no edge from to . But how do we iterate over all vertices in when we only know the size? This is where nondeterminism comes into play. The idea is to iterate over every vertex in and nondeterministically guess whether it belongs to . If we guess no, we do nothing; otherwise, we verify that the vertex actually belongs to by finding a certifying path (using the same approach we used to show ). After we have guessed for every vertex in , we additionally verify that the number of yes-guesses matches . If we verify successfully, then we must have seen every vertex in in the process, and, hence, certified .

We compute in a similar fashion. For any vertex , belongs to if and only if there exists some edge to from a vertex in . Thus, it suffices to iterate over all vertices in and increment a counter when we find an edge to the vertex from some node in using the same procedure described above.

So we're essentially done! We have described an inductive procedure to certify in nondeterministic log-space. A bit more work can be done to justify that the procedure is correct and that it indeed runs in log-space, but I'll leave that as an exercise to the reader. We now conclude as desired.

NL = co-NL

We spent a great deal of time talking about graph connectivity problems. How does this help us show ? We are incredibly close. Recall we mentioned that is -complete; the -hardness proof is as follows.

Consider some arbitrary problem and a nondeterministic log-space Turing machine that decides it. The Turing machine has a poly-sized configuration graph, i.e. a graph with nodes as configurations of the Turing machine and edges as valid transitions between configurations. We reduce to by simply constructing the configuration graph, setting as the initial state, and as the accepting state (without loss of generality we can assume that the configuration graph has a unique accepting state as any Turing machine can be modified to clear its tape before accepting). Correctness of the reduction follows almost immediately from definition.

It follows that is complete. Since we have shown to be in , we have ; a symmetric argument gives us and hence . We are done!

Results Related to Alternating Space

From Immerman-Szelepcsényi we can prove that the "log-space hierarchy" collapses to ; similar arguments can be used to prove results about space-alternating hierarchies. This is a topic for a later post! I am very tired now.

(－.－)...zzz - Aaron