CS154 Assignment #7 and CS154N Asssignment #3

Practice Homework --- Not To Be Handed In

1. The clique problem --- does a given graph G have a clique (set of nodes with all possible edges between any two of them present) of size k --- is NP-complete. Prove this fact by reducing the problem IS (independent set, as discussed in Section 10.4.2) to the clique problem.

2. Suppose there are polynomial-time reductions from problem A to problem B, from B to C, and from D to C. Let S be the subset of {A,B,C,D} that have polynomial-time algorithms. What are all the possible subsets S could be?

3. (This is easy; don't look for anything deep.) Let Q be the property of RE languages L: ``L is in NP but not in P.'' Prove that Q is decidable if and only if P=NP. Remember to prove both directions of the ``if and only if.''

4. SAT100 is the satisfiability problem restricted to expressions with at most 100 variables. What can you say about the NP-completeness of SAT100?

5. Prove that if the complement of even one NP-complete problem is in NP, then NP = co-NP (and therefore the complement of every NP-complete problem is in NP).