NL = coNL

We show that  is in  and thereby establish that every problem in coNL is also in  because is NL-complete. The  algorithm  that we present for  must have an accepting computation whenever the input graph  does not contain a path from  to .

First, let's tackle an easier problem. Let  be the number of nodes in  that are reachable from  We assume that  is provided as an input to  and show how to use  to solve . Later we show how to compute .

Given  and  the machine  operates as follows. One by one,  goes through all the  nodes of  and nondeterministically guesses whether each one is reachable from  Whenever a node  is guessed to be reachable,  attempts to verify this guess by guessing a path of length  or less from  to  If a computation branch fails to verify this guess, it rejects. In addition, if a branch guesses that  is reachable, it rejects. Machine  counts the number of nodes that have been verified to be reachable. When a branch has gone through all of G's nodes, it checks that the number of nodes that it verified to be reachable from  equals  the number of nodes that actually are reachable, and rejects if not. Otherwise, this branch accepts.

In other words, if  nondeterministically selects exactly  nodes reachable from  not including  and proves that each is reachable from  by guessing the path,  knows that the remaining nodes, including  are not reachable, so it can accept.

Next, we show how to calculate  the number of nodes reachable from  We describe a nondeterministic log space procedure whereby at least one computation branch has the correct value for  and all other branches reject.

For each  from 0 to  we define  to be the collection of nodes that are at a distance of  or less from  (i.e., that have a path of length at most  from  ). So  each  and  contains all nodes that are reachable from  Let  be the number of nodes in  We next describe a procedure that calculates  from Repeated application of this procedure yields the desired value of 

We calculate  from  using an idea similar to the one presented earlier. The algorithm goes through all the nodes of  determines whether each is a member of  and counts the members.

To determine whether a node  is in  we use an inner loop to go through all the nodes of  and guess whether each node is in  Each positive guess is verified by guessing the path of length at most  from  For each node  verified to be in  the algorithm tests whether  is an edge of  If it is an edge,  is in . Additionally, the number of nodes verified to be in  is counted. At the completion of the inner loop, if the total number of nodes verified to be in  is not  all  have not been found, so this computation branch rejects. If the count equals  and  has not yet been shown to be in  we conclude that it isn't in . Then we go on to the next  in the outer loop.

This algorithm only needs to store  and a pointer to the head of a path at any given time. Hence it runs in log space.