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).