CS 262: Computational Complexity Homework 3
1. A directed graph G = (V, E) is strongly connected if for every pair of verties (x, y), there is a directed path from x to y and a directed path from y to x. Define STRONGLYCONN to be the language consisting of all graphs that are strongly connected. Either show that this problem is in L or show a complexity consequence that results if this problem is in L.
2. A strong nondeterministic Turing Machine has, in addition to qacc and qrej states, a special state q?. The state q?, like qacc and qrej , is a terminating state in that there are no transitions out of state q?. A strong NTM accepts its input if all computation paths lead to qacc or q? states. A strong NTM rejects its input if all computation paths lead to qrej or q? states. Also, on each input, there is at least one computation path that leads to qacc or qrej . In order for a language L to be decided by a strong NTM, the NTM must accept or reject every input x according to whether x ∈ L. Note that the fact that a strong NTM decides a language implies that there can be no input that has compuation paths that lead to both qacc and qrej . Show that the class of languages decided by a strong nondeterministic Turing Machine in polynomial time is exactly NP ∩ co-NP.
3. An alternative definition of the class NL makes use of a Turing Machine with a special read-once tape. The head on a read-once tape starts at the left-most end of the nonblank symbols written on the tape and can only move to the right or stay in the same place (i.e. it can never move left). The alternative definition says that a language L is in NL if there is a deterministic Turing Machine R (called a verifier) with a special read-once tape and a polynomial p such that for every x ∈ Σ ∗ ,
x ∈ L ⇔ ∃u ∈ Σ p(|x|) such that R(x, u) = 1,
where R(x, u) is the output of R when x is placed on the input tape and u is placed on its special read-once tape and R uses O(log n) space on its work tape for every input x.
Prove that this definition of NL is equivalent to the definition using non-deterministic Turing Machines discussed in class.