CS Theory Homework Problems
1. Is Ld reducible to Lu? Prove your answer.
2. Let A, B, and C be three languages. If there is a polynomial-time reduction from A to B and a polynomial-time reduction from B to C, then is there a polynomial-time reduction from A to C?
3. How many solutions does this instance of Post's Correspondence Problem (PCP) have?
A = ab, abaaa, a
B = b, ab, aaa
4. Is PCP over a unary alphabet decidable or undecidable? Prove your answer.
5. A useless state in a Turing machine is one that is never entered during a computation on any input. Let M be a TM with no useless states. Is L(M) (a) recursive, (b) RE but not recursive, or (c) not RE? Prove your answer.
6. Prove that P is closed under complement. Explain why your proof fails to show that NP is closed under complement.
You can discuss problems with others but your answers must be in your own words. Late assignments cannot be accepted.