Computational Complexity: COMPSCI 750 Semester 2, City Campus

Prerequisites: CompSci 320 or CompSci 350 or equivalent

Assessment: 50% exam; 30% test; 20% assignments

Description: This is a survey paper of the popular computational complexity classes including and beyond P and NP.

Contents:
Definitions of computational models and complexity classes: time complexity (e.g. P and NP), space complexity (e.g. L and PSPACE), interactive complexity (IP), probabilistic complexity (BPP), circuit complexity, polynomial-time hierarchy (PH), parallel complexity (NC), fixed-parameter complexity, and program-size complexity.

Highly recommended for all graduate students interested in theoretical computer science.

Taught: Second semester, three lectures per week

Timetable: Lectures: MWTh 10-11am, CS Seminar Room (Rm303.279, Maths/Physics Bldg)

Textbook: M. Sipser. Introduction to the Theory of Computation, PWS Publishing Company, Boston, 1st or 2nd edition.

Recommended Reading:

• Structural Complexity I by J.L. Balcazar, J. Diaz and J. Gabarro (Springer-Verlag 1995)
• Computational Complexity by C. Papadimitriou (Addison-Wesley 1994)
• Models of Computation -- Exploring the Power of Computing by J.E. Savage (Addison-Wesley 2000)