8. (30 points).

(a) Define the complexity class, NP .

(b) Define the term NP -complete.

(c) Define INDEPENDENT-SET as the problem that takes a graph G and an integer k and asks if G contains an independent set of vertices of size k . That is, G contains a set W of vertices of size k such that, for any u and v in W , there is no edge ( u, v ) in G . Show that INDEPENDENT-SET is NP -complete (remember that there are two parts to this). You may assume the NP -completeness of either VERTEX-COVER or 3SAT for the sake of this proof.