Skip to Content

TU Wien Fakultät für Informatik DBAI Database and Artificial Intelligence Group
Top-level Navigation: Current-level Navigation:

Path: DBAI > education > Komplexit´tätstheorie

Tools: Drucken


Komplexitätstheorie

VU 181.142 (2.0) Sommersemester 2017

Reinhard Pichler


Table of Contents
News

General information


Registration and Admission


Course overview

The most fundamental notions and results of complexity theory have already been covered in the lecture Formale Methoden der Informatik (185.291): In the first part of the Komplexitätstheorie lecture, these topics will be revisited and additional details will be provided such as In the second part of the Komplexitätstheorie lecture, further topics will be touched on such as


Schedule of lectures (preliminary plan)

Lecture Date/Place Topic Slides Supplementary material
1 Tuesday, 07-March
11:00 - 13:00
Seminarraum 188/2
General Information,
short recapitulation of the lecture
Formale Methoden der Informatik (185.291)
cc01, 4x1
cc02, 4x1
Thursday, 09-March
16:00 - 18:00
HS11 Paul Ludwik,
Main Building
Quiz, first attempt


2 Tuesday, 14-March
11:00 - 13:00
Seminarraum 188/2
Logarithmic Space
cc03, 4x1 [Pap94] Chap. 7, 8
Thursday, 16-March
16:00 - 18:00
HS11 Paul Ludwik,
Main Building
Quiz, second attempt


Tuesday, 21-March no class


3 Tuesday, 28-March
11:00 - 13:00
Seminarraum 188/2
Boolean Logic

Homework 1 (pdf, tex)
cc04, 4x1 [Pap94] Chap. 4, 9
4 Tuesday, 04-April
11:00 - 13:00
Seminarraum 188/2
Boolean Logic (continued)

Homework 2 (pdf, tex)


5 Tuesday, 25-April
11:00 - 13:00
Seminarraum 188/2
NP-Completeness

cc05, 4x1 [Pap94] Chap. 9
6 Tuesday, 02-May
11:00 - 13:00
Seminarraum 188/2
Parameterized Complexity (Introduction)

Reading assignment 1 (pdf)
sccc2013, 4x1
7 Tuesday, 09-May
11:00 - 13:00
Seminarraum 188/2
Polynomial Hierarchy [Pap94] Chap. 17
8 Tuesday, 16-May
11:00 - 13:00
Seminarraum 188/2
Polynomial Hierarchy (continued)


9 Tuesday, 23-May
11:00 - 13:00
Seminarraum 188/2
Polynomial Hierarchy (continued)
10 Tuesday, 30-May
11:00 - 13:00
Seminarraum 188/2
Complexity of Logic-Based Abduction [EG95]
Tuesday, 06-June no class (pentecost holidays)


11 Tuesday, 13-June
11:00 - 13:00
Seminarraum 188/2
Complexity of Logic-Based Abduction (continued)
12 Tuesday, 20-June
11:00 - 13:00
Seminarraum 188/2
PSPACE [Pap94] Chap. 19
13 Tuesday, 27-June
11:00 - 13:00
Seminarraum 188/2
PSPACE (continued)

Assessment

Assessment will be based on the quiz at the beginning of the term, homework assignments, reading assignments and an exam at the end of the term. Detailed information will be provided in the first class.

Books and further references

Textbooks

Christos H. Papadimitriou: Computational Complexity. Addison Wesley, 1994. (Abbr. [Pap94])

Michael R. Garey, David S. Johnson: Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979. (Abbr. [GJ79])

Articles: Overview, Motivation

David S. Johnson: A Catalog of Complexity Classes. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) pp. 67-161 (1990).

Heribert Vollmer: Was leistet die Komplexitätstheorie für die Praxis? Informatik Spektrum 22 Heft 5 (1999).

Stephen Cook: The Importance of the P versus NP Question. Journal of the ACM, 50(1):27-29 (2003).

Further Articles: Some complexity results treated in this lecture

Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov: Complexity and Expressive Power of Logic Programming. ACM Computing Surveys 33(3):374-425 (2001).

Thomas Eiter and Georg Gottlob: The Complexity of Logic-Based Abduction. Journal of the ACM, 42(1):3-42 (1995).

Miki Hermann and Reinhard Pichler: Counting Complexity of Propositional Abduction. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07), pp. 417-422 (2007).

Online Notes

Oded Goldreich et al.: Introduction to Complexity Theory.


Last modified 26 February, 2017