Complexity Theory studies the computational properties of decision problems. In this course, we introduce some of
the most important notions of complexity theory. We define the basic complexity classes (P, NP, PSpace, etc.) and
provide tools for showing that a problem belongs to, or is as hard as any problem in these classes.

The course is aimed to students with little or no knowledge of the topic.

Chair of Automata Theory

Institute of Theoretical Computer Science

Faculty of Computer Science

Technische Universität Dresden

Institute of Theoretical Computer Science

Faculty of Computer Science

Technische Universität Dresden

# Introduction to Complexity Theory

## Dr. Rafael Peñaloza

### Course Description

### Organisation

The lecture takes place once a week in room E05:

*Wednesdays 9:20–10:50*.*Announcements:*~~On~~*9th July*, there will be a*lecture*instead of an exercise session.~~On~~*25th June*, there will be a*lecture*instead of an exercise session. In return, on*27th June*, there will be an*exercise session*.~~On~~*13th June*, there will be an*exercise session*instead of a lecture.~~On~~*23rd May*, there will be an*exercise session*instead of a lecture.~~On~~*30th April*, there will be a*lecture*instead of an exercise session.~~The exercise session will start on~~*16th April*.~~The lecture will start on~~*4th April*.

### SWS/Modules

*SWS:*2/1/–

This course can be used in the following

*modules:*

- Bachelor-Studiengang Informatik:
*INF-B-510*(Vertiefung),*INF-B-520*(Vertiefung zur Bachelor-Arbeit) - Master/Diplom-Studiengang Informatik:
*INF-BAS6*(Theoretische Informatik),*INF-VERT6*(Theoretische Informatik) - Master in Computational Logic:
*MCL-TCSL*(Theoretical Computer Science and Logic),*MCL-PI*(Principles of Inference),*MCL-KR*(Knowledge Representation),*MCL-MV*(Modeling and Verification) - Diplom-Studiengang Informatik (Studienordnung 2004): Fachgebiet
*Theorie der Programmierung*, Fachgebiet*Intelligente Systeme*

### Exercises

An exercise session will be held every second week by
Marcel Lippmann
on

Exercise sheets will be available here approximately one week before the session.

*Mondays 9:20–10:50*in room E05.Exercise sheets will be available here approximately one week before the session.

- Exercise Sheet 1 (16th April); Solution for Ex. 1, which can be read using JFLAP
- Exercise Sheet 2 (14th May)
- Exercise Sheet 3 (23rd May)
- Exercise Sheet 4 (11th June)
- Exercise Sheet 5 (13th June)
- Exercise Sheet 6 (27th June)

### Literature

The following books are relevant for the lecture:

- Christos H. Papadimitriou.
*Computational Complexity*, Addison Wesley, 1994. - Michael Sipser.
*Introduction to the Theory of Computation*, PWS, 1997.