Data structures and program structures

MCS 541, Computational Complexity, Fall 1999

**19990910:**
Homework due 19990917.
Problem 2.8.17, in case of 3-tape deterministic Turing machine.

**19990922:**
Homework due 19990929.
Problem 7.4.3(a).
Problem 7.4.6: Prove that NP and P are closed under star.

**19991006:**
Homework due 19991018.
Problem 4.4.5.
Problem 4.4.14.

**19991008:**
Homework due 19991022.
Problem 8.4.2: Prove that there are no P-complete problems
under linear-time reductions.
Problem 8.4.3: Prove that P, NP, coNP, LOGSPACE, NLOGSPACE, PSPACE, and EXPTIME
are closed under (logspace) reductions.

**19991029:**
Homework due 19991108.
Problem 9.5.2: Give a *simple* reduction from SAT to 3SAT.
Problem 9.5.4(a).

**19991119:**
Homework due 19991201.
Problem 15.5.3.
Problem 15.5.6(a).