## Complexity Theory

### Quick information

- Personnel:
- Lecturer: Helger Lipmaa
- Tutorials: Prastudy Fauzi

- Timetable:
- Lectures: Fridays, 12:15-14:00 (Liivi 2-611)
- Tutorials: Wednesdays, 16.15 - 18.00 (Liivi 2-611)

- Languages: English

### Introduction

Goals: to teach students to recognize problems, which can not be solved in polynomial time. a) Notions - nondeterministic Turing machine, time and space complexity, complexity classes P and NP, NP-complete languages. b) Skills - to recognize NP-hard problems and prove NP-completeness of the problems.

This time, the course will be based on the following textbook:

- Christos H. Papadimitriou, http://www.amazon.co.uk/Computational-Complexity-Christos-H-Papadimitriou/dp/0201530821? (1994)

### Learning outcomes

After taking the course, you master the key complexity classes, their underlying models of computation, and relationships. You are able to formalize and abstract from a given computational task relevant computational problems and argue that they belong to appropriate complexity classes. You understand the concept of reductions and how it can be used to order problems by their computational complexity. You are able to show using reductions that a problem is complete for a central complexity class (such as NP) and you understand the importance and implications of such a result. You are familiar with the concepts of randomized, approximation, and parallel algorithms and aware of related complexity classes and their relation to other complexity classes and their models of computation.

(As this is the first time to teach according to that textbook, the exact contents of the course will be come clear later, so the outcomes depend somewhat on the amount of material we are able to cover.)

### Grading

Homework (given out continuously during the course during the tutorials) will give 50% of the grade. Other 50% come from exam. The exam will be more theoretical, compared to the homeworks.