Some comments on Questions 3 and 6 of Assignment 2: For Question 3, a common error is to write C(i,X) where X is a set of inputs. This doesn't make sense. Usually in this place people want to verify that X' is the intersection of S_i and X, and they need to show that this can be done in polynomial time. For Question 6, a few people have problem with showing that UDIST is in NL. Recall that (G,s,t,d) is in UDIST iff the distance between s and t is exactly d. To verify this, we need to verify that (i) there is a path from s to t of length d, and (ii) that there is no shorter path. Now (i) can be done by providing a certificate which is a path of length d. For (ii) you cannot simply run a nondeterministic procedure which guesses a path, and accept if the procedure reject. (Because, say, there is a path of length 1 < d, but the nondeterministic procedure doesn't guess the right choice.) For (ii) you need to use the fact that NL = co-NL. By the same argument that PATH is in NL, it is easy to see that part (ii) can be done in co-NL (because its complement is in NL). Now NL = co-NL implies that (ii) can be done in NL. Some other people argue that UDIST is in NL because they can enumerate all path of length d. This is problematic, because the number of such path can be exponential in the input size, and there is no way of enumerating them if you cannot hold the count of how many you have seen so far.