We finished talking about the theory of NP-completeness; if you like that material, check out CSC 489 Theory of Computation, which Dr. Kanj is teaching next quarter..

Submission: you can submit the homework to me either by hardcopy in class or email it to me.

1. [k-colorability, 25pt] Assuming that 3-colorability is NP-complete, show that k-colorability is NP-complete for any k >= 3. Also show that 2-colorability is in P.

2. [2CNF, 15pt] 2CNF-SAT is the problem of deciding whether a formula in 2CNF is satisfiable; 2CNF means, the formula is in conjunctive normal form, and each clause contains at most two literals. Show that 2CNF-SAT can be solved in polynomial time. Hint: clauses with one literal are easy; if you have a clause with two literals, such as (x v y) think of it as an implication, that is, (not-x -> y). Now rephrase the problem as a problem on graphs.

3. [Hamiltonian Path, 15pt] Show that the Hamiltonian Path problem is NP-complete. HP = {(G,u,v): there is a Hamiltonian Path from u to v}.

4. [Longest Path, 15pt] Show that the Longest Path Problem is NP-complete, where LP = {(G,u,v,k): there is a path of length at least k from u to v in G}.

5. [Extra Credit] Show that the coin changing problem is NP-complete, that is: CC = {(d₁, d₂, ..., d_n, v, k): can you make change for amount v using at most k coins chosen from denominations {d₁, d₂, ..., d_n})?}. Hint: reduce from subset-sum.