CSE 237, Spring 2006
Homework 11a
due 4/28/06 in review session

• Do not submit problems whose answers are in the textbook

• Start each problem on a new sheet.

• You can make use of any theorem that was presented/proved in class.

• You are encouraged to discuss the homework problems in groups -- as long as you do the writing by yourself.

Problem 1. Rice's theorem

(a) Can we use Rice's theorem to show that EQ_TM is undecidable? Explain.

(b) Let FINITE_TM be the following language:

     FINITE_TM = {<M> : M is a Turing machine whose language is finite}

Use Rice's theorem to show that FINITE_TM is undecidable

Problem 2. Mapping reducibility

(a) Using the fact that E_TM is co-recognizable, prove that E_TM is not recognizable.

(b) 5.5 -- use the result proved in (b) (solution in textbook).

Problem 3. Post Correspondence Problem (PCP)

(a) Problem 5.3

(b) Show that PCP is recognizable.
Hint: how can we find a match if one exists?

(c) Unary PCP is a version of PCP where the alphabet is unary. That is, S = {1}, and both the top and bottom of each domino are strings from 1*.  Show that Unary PCP is not only decidable, but is in P.
Hint: do we need to know both strings for each domino or can we simplify the problem?

Problem 4. P and NP

(a) Show that P is closed under union.

(b) Show that P is closed under concatenation.

(c) Show that NP is closed under star, by describing, for any L in NP, a polynomial-time nondeterministic algorithm that accepts L*.

Note: In fact, both P and NP are closed under union, concatenation, and star.  P is also closed under complement, but it is not known whether NP is closed under complement; it depends on whether P = NP.