CS154 Assignment #7 Solutions

1. Take a graph G and integer k that is an instance of the IS problem. From these construct a graph G' formed from G by complementing the set of edges. That is, there is an edge (x,y) in G' if and only if there is not an edge (x,y) in G. The pair consisting of G' and the integer k is an instance of CLIQUE.

   In proof, if G has an independent set of size k, then there are no edges among these nodes in G. Thus, all the edges among these nodes are in G', where they form a clique of size k.

   Conversely, if G' has a clique of size k, then in G there are no edges among these nodes, so they are an independent set in G.

2. If C has a polynomial-time algorithm, then they all do. If C does not have a polynomial-time algorithm, then all combinations of {A,B,C} are possible, except that if B has a polynomial-time algorithm, then A does. Thus, the possible sets are ABCD, ABD, AB, AD, D, A, and the empty set.

3. Rice's theorem says every nontrivial property of the RE languages is undecidable. If P != NP, then the property is nontrivial, hence undecidable. If P = NP, then there is an obvious decision algorithm: ``just say no.''

4. There are ``only'' 2^100 truth assignments to check, so we can test satisfiability in O(n) time for expressions of length n. Of course the big-oh hides a rather large constant!

5. The key point is that if P reduces to Q, then the -P (we use - for ``complement of'') reduces to -Q by the same transformation. Suppose Q is an NP-complete problem that is in co-NP. Then every problem P in NP is in co-NP; just transform -P to -Q in polynomial time and then use the nondeterministic polynomial-time algorithm for -Q to solve -P in nondeterministic polynomial time. Thus, P is in co-NP. That shows NP is contained in co-NP.

   For the other half of the equality NP = co-NP, suppose P is in co-NP. That is, -P has a nondeterministic polynomial-time algorithm. Since Q is NP-complete, there is a polynomial-time reduction of -P to Q, and thus, such a reduction from P to -Q. Since Q is in co-NP, -Q is in NP, and thus so is -P. That shows co-NP is contained in NP, and we now have NP = co-NP.