Meeting Time:
Mon 121 in CIT 506,
Wed & Fri 34 in the CIT 4th floor library
Course Description:
Syllabus
Proposal (doc)
Lecture Schedule(ps)
Lectures:

Lecture 1: Introduction, Turing Machine (kmmatule, coming soon)
 Lecture 2: More TMs (kmmatule, draft)
dvi
ps
pdf

Lecture 3: Decidability (scanon, halfdone):pdf

Lecture 4: Undecidability and PCP (dpierce):html
doc

Lecture 5: Self reference and Recursion Theorem (bmares, erachlin):
dvi
ps
pdf

Lecture 6: Introduction to Complexity theory (jalper):
pdf

Lecture 7: NP completeness (ewbaer):

Lecture 8: PSPACE completeness (msbean):
doc
 Lecture 9: Diagonalization and Space/Time Hierarchy Theorems
dvi
ps
pdf
 Lecture 10: Alternation (apienaar):

Lecture 11: IP=PSPACE (bmares):
jpg

Lecture 12: ZeroKnowledge & PCP (apienaar,erachlin)
Homeworks:

HW1: Design a TM that decides {0^{n}1^{n} n >=
0}, do 3.103.13 (one of), 3.16,3.19
Solutions (dvi, ps,
pdf)

HW2: Do exercises 4.15, 5.17, 5.20
Solutions (dvi, ps, pdf)

HW3:To be found here: dvi ps pdf
Solutions (dvi,
ps,
pdf)

HW4: Do exercises 7.28 and 7.29. Additionally, convince yourself coNP = NP is not necessarily true.
Argue that if coNP is not equal to NP, then P is not equal to NP
Solutions (dvi,
ps,
pdf)

HW5: Do exercises 7.34 and 8.11
Solutions (dvi,
ps,
pdf)

HW6: Do exercises 8.13, 8.19, 8.20
Solutions (dvi,
ps,
pdf)

HW7: Do exercises 9.13, 9.11
Solutions (dvi,
ps,
pdf)

HW8: Do exercises 10.12, and 10.14
Solutions (dvi,
ps,
pdf)

HW9: Do exercises 10.11, and one of 10.15 & 10.16
(for 10.16, note the errata in Sipser)
Solutions (dvi,
ps,
pdf)

Links and Handouts:
Papers:
 A Detailed Proof That IP=PSPACE (bmares):
dvi
ps
pdf
 Oracle Theory (jalper):
dvi
ps
pdf
tex
bibtex
 Diagonalization and Relativization:
Why P vs NP ain't as easy as it looks (kmmatule):
dvi
ps
pdf
 P, NP, and Logic (erachlin)
doc
html
 Parallel Computation and Equivalence between PRAMs and Circuits (ewbaer):
dvi
ps
pdf

