### 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