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 2018

Reinhard Pichler


Table of Contents
News
Registration in TISS is open
(until 6 March, 2018)

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 (as time permits) such as


Schedule of lectures (preliminary plan)

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


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


3 Tuesday, 20-March
11:00 - 13:00
Seminarraum 188/2
Boolean Logic
[Pap94] Chap. 4, 9
4 Tuesday, 10-April
11:00 - 13:00
Seminarraum 188/2
Boolean Logic (continued)


5 Tuesday, 17-April
11:00 - 13:00
Seminarraum 188/2
NP-Completeness
[Pap94] Chap. 9
6 Tuesday, 24-April
11:00 - 13:00
Seminarraum 188/2
NP-Completeness (continued)


Tuesday, 01-May no class (public holiday)


7 Tuesday, 08-May
11:00 - 13:00
Seminarraum 188/2
Polynomial Hierarchy

[Pap94] Chap. 17
8 Tuesday, 15-May
11:00 - 13:00
Seminarraum 188/2
Polynomial Hierarchy (continued)
Tuesday, 22-May no class (pentecost holidays)


09 Tuesday, 29-May
11:00 - 13:00
Seminarraum 188/2
Complexity of Logic-Based Abduction [EG95]
10 Tuesday, 05-June
11:00 - 13:00
Seminarraum 188/2
Complexity of Logic-Based Abduction (continued)
Tuesday, 12-June no class


11 Tuesday, 19-June
11:00 - 13:00
Seminarraum 188/2
PSPACE [Pap94] Chap. 19
Thursday, 21-June
09:00 - 11:00
Seminarraum 183/2
Written exam
12 Tuesday, 26-June
11:00 - 13:00
Seminarraum 188/2
PSPACE (continued)
Thursday, 28-June
09:00 - 12:00
Institute 192 (3rd floor)
Oral exam

Assessment

Assessment will be based on the quiz at the beginning of the term and a written exam as well as an oral 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 18 February, 2018