Lecture 4

Assignment 1 posted on Assignments page, due Friday, October 8.

Scribe Notes by Greg Stoddard.

Lecture 3

Scribe Notes by Michele Budinich

Compendium of Complete Problems in Second Level and Higher (Schaefer and Umans)

Relevant Papers:

1. S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982.
2. M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing volume 20, pp.471–483. 1991.

Lecture 2

Ladner's Theorem
Two Proofs of Ladner's Theorem

Lecture 1

The P versus NP Problem.
Scribe Notes by Nicolas Renold