View a video preview of this course
Course Description:
Develops a quantitative theory of the computational difficulty of problems in terms of the resources (eg. time, space) needed to solve them. Classification of problems into complexity classes, reductions and completeness. Power and limitations of different modes of computation such as nondeterminism, randomization, interaction and parallelism.
Faculty/Manager:
Rocco Servedio
Contact Information:
Rocco Servedio
email: ras2105@columbia.eduClass Homepage: http://www.cs.columbia.edu/~rocco/Teaching/S10/cs4236/ Credits for Course: 3 Viewing Schedule: 3 lectures per week Prerequisites: Computer Science Theory (COMS W3261) Required Text(s): C.H. Papadimitriou. Computational Complexity Grading: Biweekly Problem Sets (70% of grade)
Take-home Final Exam (30% of grade) Notes: There is a schedule with more detailed information available from the course website.
* The information contained in this syllabus is subject to change at any time.