Instruction
| Name | Cr | Method of study | Time | Location | Organiser |
|---|---|---|---|---|---|
| Complexity theory | 10 Cr | General Examination | 8.1.2020 - 8.1.2020 | ||
| Complexity theory | 10 Cr | General Examination | 11.12.2019 - 11.12.2019 | ||
| Complexity theory | 10 Cr | Lecture Course | 6.9.2019 - 13.12.2019 | ||
| Complexity theory | 10 Cr | Examinarium (electronic exam room) | 27.4.2018 - 31.5.2018 | ||
| Complexity theory | 10 Cr | General Examination | 11.4.2018 - 11.4.2018 | ||
| Complexity theory | 10 Cr | General Examination | 10.1.2018 - 10.1.2018 | ||
| Complexity theory | 10 Cr | General Examination | 13.12.2017 - 13.12.2017 | ||
| Complexity theory | 10 Cr | Lecture Course | 4.9.2017 - 13.12.2017 |
Target group
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.
Prerequisites
Routine in mathematics
Learning outcomes
The course is an introductory course to computational complexity theory.
Timing
Recommended time/stage of studies for completion: 1. or 2. year
Term/teaching period when the course will be offered: varying
Contents
Turing machines, basic complexity classes, hierarchy theorems, reductions and completeness
Activities and teaching methods in support of learning
Lectures and exercise classes
Study materials
C. H. Papadimitriou: Computational complexity (1994); S. Arora and B. Barak: Computational complexity: a modern approach (2009)
Assessment practices and criteria
Exam and excercises, Course will be graded with grades 1-5
Recommended optional studies
Master studies
Completion methods
Exam, other methods will be described later