Kaisa_2012_3_photo by Veikko Somerpuro

Complexity theory

This course is an introduction to computational complexity. During the course you will learn how computational problems are categorised into complexity classes and how hardness of problems is compared. You will also learn basic complexity classes and techniques for proving complexity results.
After the course you will not only know what the P vs NP problem is all about, you will also have a deeper understanding of how it is related to other complexity questions, as well as of what limitations common proof techniques have in tackling it.

Ilmoittaudu

Viestit

Åsa Hirvonen

Julkaistu, 16.11.2019 klo 10:08

Please note the schedule of the last weeks:
- no classes on 6.12. (independence day)
- exercise class on Monday 9.12.
- exam on Wednesday 11.12. - note that you need to sign up separately for the exam by 1.12. (another exam possibility is offered in January)
- go-through of the exam questions on Friday 13.12. at 10-12 (I don't know whether I have the exam papers yet then, but we will go through what the answers were supposed to contain)
- no exercise class on Friday 13.12.

Åsa Hirvonen

Julkaistu, 30.8.2019 klo 9:38

Please note that although there is no lecture on Monday 2.9. (due to the university opening festivities), the course has an exercise class already on the first week (see the Tasks section). In the meantime, read the introduction and chapter 0 of the book (intro + chapter 1.1 of web draft).

Aikataulu

Timetable in short:

Lectures
Monday 14-16, B119
Friday 10-12, BK106

Exercises
Friday 14-16, BK106

The last exercise class is on Monday 9.12. (there are no classes on 6.12.) and on Friday 13.12. 10-12 we go through the exam questions. The exercise class session on Friday 13.12. is cancelled.

PäivämääräAikaOpetuspaikka
Pe 6.9.2019
10:15 - 12:00
Ma 9.9.2019
14:15 - 16:00
Pe 13.9.2019
10:15 - 12:00
Ma 16.9.2019
14:15 - 16:00
Pe 20.9.2019
10:15 - 12:00
Ma 23.9.2019
14:15 - 16:00
Pe 27.9.2019
10:15 - 12:00
Ma 30.9.2019
14:15 - 16:00
Pe 4.10.2019
10:15 - 12:00
Ma 7.10.2019
14:15 - 16:00
Pe 11.10.2019
10:15 - 12:00
Ma 14.10.2019
14:15 - 16:00
Pe 18.10.2019
10:15 - 12:00
Ma 28.10.2019
14:15 - 16:00
Pe 1.11.2019
10:15 - 12:00
Ma 4.11.2019
14:15 - 16:00
Pe 8.11.2019
10:15 - 12:00
Ma 11.11.2019
14:15 - 16:00
Pe 15.11.2019
10:15 - 12:00
Ma 18.11.2019
14:15 - 16:00
Pe 22.11.2019
10:15 - 12:00
Ma 25.11.2019
14:15 - 16:00
Pe 29.11.2019
10:15 - 12:00
Ma 2.12.2019
14:15 - 16:00
Ma 9.12.2019
14:15 - 16:00
Pe 13.12.2019
10:15 - 12:00

Muu opetus

06.09. - 18.10.2019 Pe 14.15-16.00
01.11. - 29.11.2019 Pe 14.15-16.00
Åsa Hirvonen
Opetuskieli: englanti

Materiaalit

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/

Another good text is
C. H. Papadimitriou: Computational complexity (1994)

Tehtävät

Kurssin suorittaminen

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 (11.12. at 16-19). A second possibility is offered in the January general exam. Please note that you need to sign up for the exam separately.

Kuvaus

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