Archive for the ‘Homework’ Category

Homework #1

April 5, 2010

Due: Monday, April 19, at the beginning of class. Turn in physically or by email to Thach.

Remember to take a look at the grading guidelines.

In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that each submission can have at most one author. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.

The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools.  Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.

Most of the problems only require one or two key ideas for their solution.  It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.

A final piece of advice:  Start working on the problem sets early!  Don’t wait until the day (or few days) before they’re due.


Each problem is worth 15 points unless otherwise noted.

  1. Exercise 2.8 from the text: Let HALT be the Halting Language defined in Theorem 1.11 of the text: HALT = \{ a,x | M_a(x) \text{ halts in a finite number of steps} \}. Show that HALT is NP-hard. Is it NP-complete?
  2. Exercise 2.10 from the text: Suppose L_1, L_2 are in NP. Then is L_1 \cup L_2 in NP? What about L_1 \cap L_2?
  3. Exercise 2.15 from the text: A clique of an undirected graph is a set of vertices in which every two vertices have an edge between them. A vertex cover is a subset such that every edge of the graph is incident to one of the vertices from the set. Let CLIQUE be language \{G,k | \text{ the graph G has a clique of size k } \} , and let VERTEX COVER be the language \{ G,k | \text{the graph G has a vertex cover of size k} \} . Prove that both of these problems are NP-complete.
  4. Exercise 3.9 from the text: Suppose we pick a random language C by choosing every string to be in C independently with probability 1/2. Prove that with high probability P^C is not the same as NP^C .
  5. A digital signature scheme is a triple of randomized polynomial time algorithms: Generate, Sign, and Check, with the following properties. On input  1^n , Generate outputs a pair of strings (public, secret), such that for any message m, Check(m,Sign(m,secret),public) always outputs 1, yet for any polynomial time algorithm A, the probability that Check(m,A(m,public),public) outputs 1 is at most O(n^{-100}) . Show that such a scheme cannot exist if P=NP.