Messages
Timetable
Material
We follow approximately chapters 1-5 of the book Arora, S., Barak, B. Computational Complexity: A Modern Approach. A draft of the book is available on the authors' page http://theory.cs.princeton.edu/complexity/
Other recommended texts are
C. H. Papadimitriou: Computational complexity (1994)
J. Paris: Computational Complexity (lecture notes, 2007-08), available at http://www.maths.manchester.ac.uk/~jeff/lecture-notes/MATH63011.ps
Tasks
Exercises
Conduct of the course
The course is evaluated based on a final exam and the exercises the student solved during the course.
The course exam will be organized in the December general exam of the department (13.12. at 16-20). A second possibility is offered in the January general exam.
Description
Optional course.
Master's Programme in Mathematics and Statistics is responsible for the course.
The course belongs to the Mathematics and Applied mathematics module.
The course is available to students from other degree programmes.
Routine in mathematics
Master studies
The course is an introductory course to computational complexity theory.
Recommended time/stage of studies for completion: 1. or 2. year
Term/teaching period when the course will be offered: varying
Turing machines, basic complexity classes, hierarchy theorems, reductions and completeness
C. H. Papadimitriou: Computational complexity (1994); S. Arora and B. Barak: Computational complexity: a modern approach (2009)
Lectures and exercise classes
Exam and excercises, Course will be graded with grades 1-5
Exam, other methods will be described later