Read Wilf, Sec 4.10, p.100-101, up to Lemma 4.10.1 (reading the lemma is optional). Right before the lemma, in (3) it says the input to algorithm A is (n,C(n)); and in (4) it says: Algorithm A runs in polynomial time. Is it "polynomial time" as a function of n? Or n + size of C(n)? Or something else? Fully support your answer. (Think carefully about this!)
In the definition of class NP in Wilf, on top of p.112, what is the input size for the algorithm? Is it “size of x”, is it “size of x plus size of C(x)”, or is it something else? Explain your reasoning.
Give the definition of each of the following (if you need to look up any of them, after doing so wait at least a few hours before writing your answers, to see if you retained them!): (i) "NP" (give both of the definitions that we have discussed); (ii) "NP-complete"; (iii) "NP-hard". (Wilf doesn’t define “NP-hard”; search the web for it.)
Explain the main differences between when a problem is in NP, is NP-hard, or is NP-complete.
Optional: Search the web to find an example of a problem that is in NP but has not been proven to be NP-complete.