A printable PDF is available.

## Assignment 5: Due Thursday, October 30

- Page 294, Exercise 7.1 (parts a,b,e,f)
- Page 295, Exercise 7.7
- Page 296, Problem 7.20
- Page 296, Problem 7.21
- Page 296, Problem 7.25
- Page 297, Problem 7.29
- 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).

- 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}*is true^{p(n)}, P(x,w)*}* - [(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}*is true^{p(n)}, P(x,w)*}*. 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*is true_{1}in {0,1}^{p(n)}exist w_{2}in {0,1}^{p(n)}, P(x,w_{1},w_{2})*}*. What can you say about the complexity of such a language (relation to P? NP? other classes?).

- [(a)] Show that