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