A printable PDF is available.

Assignment 5: Due Thursday, October 30

1. Page 294, Exercise 7.1 (parts a,b,e,f)
2. Page 295, Exercise 7.7
3. Page 296, Problem 7.20
4. Page 296, Problem 7.21
5. Page 296, Problem 7.25
6. Page 297, Problem 7.29
7. Page 299, Problem 7.44

The following problem is a "challenge problem" -- you are not required to do it, but if you get a good solution you will receive extra credit (up to 15 points).

1. The class NP can be approached from the standpoint of logic, as opposed to non-deterministic computation. We use the notion of a "polynomial-time predicate" -- a logical predicate (a function that evaluates to true or false) P(x,y) is a polynomial-time predicate if a deterministic Turing machine decides the language L={ < x,y > |P(x,y) is true} in polynomial time (or more informally, an algorithm calculates P(x,y) in polynomial time).
   • [(a)] Show that L in NP if and only if there exists a polynomial p(n) and a polynomial time predicate P(x,y) such that L={ x| exist w in {0,1}^p(n), P(x,w) is true }
   • [(b)] If we replace the existential quantifier in part (a) with a universal quantifier, we can consider the class of all languages L that can be written as L={ x| forall w in {0,1}^p(n), P(x,w) is true }. What can you say about the complexity of such an L (hint: what can you say about the complexity of L)? There's a name for the complexity class of all such L's, which is mentioned briefly in this chapter -- can you find it?
   • [(c)] Consider if you had more than one quantifier, like L={ x| forall w₁ in {0,1}^p(n)exist w₂ in {0,1}^p(n), P(x,w₁,w₂) is true }. What can you say about the complexity of such a language (relation to P? NP? other classes?).