CMSC 858: Complexity Theory

SYLLABUS:

SYLL.PS, SYLL.PDF, SYLL.HTML

NOTES ON COMPUTABILITY THEORY: NOTES.PS, NOTES.PDF

NOTES ON SPARSE SETS AND $m$-REDUCTION SPARSE.PS, SPARSE.PDF

NOTES ON POLY HIERARCHY: PH.PS, PH.PDF

NOTES ON SPARSE SETS AND TURING REDUCTION SPARSE2.PS, SPARSE2.PDF

NOTES ON SPARSE SETS AND TURING REDUCTION AND PH SPARSE3.PS, SPARSE3.PDF

NOTES ON GI AND AM GIAM.PS, GIAM.PDF

NOTE ON NUMBER OF SATISFYING ASSIGNMENTS NUMBER.PS, NUMBER.PDF

NOTE ON PCP (WARNING- these are not very good) PCP.PS, PCP.PDF

HOMEWORKS:

hw1.PS, hw1.PDF, hw1.HTML,

hw2.PS, hw2.PDF, hw2.HTML,

hw3.PS, hw3.PDF, hw3.HTML,

hw3clarify.PS, hw3clarify.PDF, hw3clarify.HTML,

hw4.PS, hw4.PDF, hw4.HTML,

hw5.PS, hw5.PDF, hw5.HTML,

hw6.PS, hw6.PDF, hw6.HTML,

midrev.PS, midrev.PDF, midrev.HTML,

hw7.PS, hw7.PDF, hw7.HTML,

hw8.PS, hw8.PDF, hw8.HTML,

hw9.PS, hw9.PDF, hw9.HTML,

hw10.PS, hw10.PDF, hw10.HTML,