Skip to content

Alan Guo: NL = coNL

by on February 20, 2012

My favorite surprising algorithm is the one that shows that NL = coNL.

The specific problem solved by the algorithm is the decision problem: Given a graph G and nodes s and t, is t unreachable from s? It’s clear that the complementary problem, deciding if t is reachable from s, is in NL since one can nondeterministically guess the path from s to t, storing only one node at a time. This problem happens to be NL-complete, so if it is shown that it is in coNL (equivalently, the unreachability problem is in NL), then it is coNL-complete, and hence NL=coNL.

The idea is as follows. Suppose in addition to G, s, and t, we know the number k of nodes reachable in G from s. Then an NL machine could do the following: guess all the nodes that are reachable from s (guessing a path for each one), and check that the number of such nodes is k and that t is not among them. This  would suffice to prove that t is not reachable from s. But how to acquire the number k? The idea is to inductively compute k(i), the number of nodes reachable from s in at most i steps, for i=1,…,n, using a similar idea. To determine if a candidate node v is reachable in i steps, we loop through all nodes and guess if they are reachable in i-1 steps, and if so, check if any of them are connected to v. If so, then v is reachable in i steps, otherwise if we already checked k(i-1) candidate nodes, then we know v cannot be reachable in i steps. We repeat for all nodes v. By the end, we will have computed k = k(n).

This algorithm is surprising since the result is quite counterintuitive (at least to me)! It is widely suspected that NP and coNP are not equal, since it seems easy to verify the existence of something but hard to verify the nonexistence of something. On the other hand, this algorithm shows that verifying existence and nonexistence are equally doable in logarithmic space.

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: