Homework

Q1. What would happen if someone discovered an NP-complete language L that was in P? Justify your answer.

Q2. Suppose we know that there is a polynomial-time reduction of a language L to SAT. What can we say about L? Justify your answer.

Q3. The game PEBBLES is played on a k × n chessboard. Initially each square of the chessboard has a black pebble, or a white pebble, or no pebble. You play the game by removing pebbles one at a time. You win the game if you can end up with a board in which each column contains only pebbles of a single color and each row contains at least one pebble.

(a) Show that the set of winnable PEBBLES games is in NP by describing a nondeterministic polynomial-time algorithm to determine whether a given PEBBLES board is winnable.

(b) Given a boolean expression E in 3-CNF with k clauses and n variables, construct the following k × n board: If literal x_i is in clause c_j, put a black pebble in column x_i, row c_j. If literal ¬x_i is in clause c­_j, put a white pebble in column x_i, row c_j. Show that E is satisfiable if and only if this PEBBLES game is winnable. [See HMU, Section 10.3.1, p. 448, for a definition of 3-CNF.]

(c) What can you conclude from (a) and (b)?

Q4. PAC-learning problem. Suppose we have a collection of 100 concepts. How many samples do we need to examine to find a true concept with an error of at most 0.1 and a probability of at least 95%?

Q5. Consider the lambda expression (λx. a x)((λy. b y) c).

(a) Identify all redexes in this expression.

(b) Evaluate this expression using normal order evaluation.

(c) Evaluate this expression using applicative order evaluation.

Q6. Let G be the function definition (λf. λx. f(f x)). Evaluate the lambda expression GG.