Section notes, Friday May 31, 2002.

Elena Nabieva

In section, I went over the proof that QTBF <= FORMULA_GAME <= GEOGRAPHY_GAME. If you have any questions, about the proofs, in particular, about the relationship between logic and games, I'll be happy to meet with you.

Finally, here is a proof that BIPARITE problem is in NL (NOT a proof of NL-completeness). This proof is based on a sample solution for a Limits of Computation class at Brown.

Note that this is a typical example of an NL problem: an NTM uses the worktape to keep track of pointers to parts of the input (in this case, numbers of nodes in the input graph) and/or a counter that goes up to O(n), where n is the size of the input. Since a number n can be represented in log (n) space, such problems are in NL.

The proof:

An undirected graph is bipartite iff you can divide all nodes into two partitions, such that the only edges are between nodes in different partitions (i.e., there is no edge between two nodes in the same partition).

1. First, we prove that BIPARTITE = HAS_NO_ODD_CYCLES. Assume that the graph is bipartite. Assume it has a cycle with an odd number, say 2k, of nodes. Pick a node in that cycle, call it n_0. Let's say that it is in the first partition. Go down the cycle in one direction, looking at which partitions the nodes belong to. Clearly, n_1 is in the second partition, n_2 in the first one, and so on. By induction, we see that all even-numbered nodes are in the first partition, and all odd-numbered nodes are in the second. Then node n_2k must be in the first partition. But since it is connected to the node n_0, we have a contradiction to the assumption that the graph is bipartite.

Now assume that the graph has no odd cycles. Pick a node, call it n_0. Label it A. Now label all of its neighbors B, all of their unlabeled neighbors A, and so on, until no nodes are left to label. These labels correspond to our two partitions. Assume that the graph is not bipartite, so some two adjacent nodes have the same label. This means that either they both have a path to n_0 involving an odd number of edges or they both have an even-length path to n_0 (namely, the paths taken when assigning labels). In either case, the path connecting them and involving n_0 has an even number of edges, and the edge connecting them directly makes it an odd cycle, leading to contradiction.

2. Because NL = coNL, the problem of showing that HAS_NO_ODD_CYCLES is in NL is equivalent to showing that HAS_ODD_CYCLES is in NL. To solve this problem, we keep a counter, originally initialized to 0, on the worktape and apply the following algorithm:

1. nondeterministically pick a node n_0 and increment the counter.

2. nondeterministically pick its neighbor, incrementing the counter.

Repeat step 2 until (a) the counter equals the number of nodes OR (b) n_0 is picked again and the counter is set to an odd number, signifying an odd cycle in the graph. If (a) occurs first, reject (the graph has no odd cycles); if (b) occurs first, accept (we found an odd cycle).

This algorithm uses log space because it only uses the work tape to keep track of the start node n_0, the neighbor node, and the counter.