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) Wintersemester 2019/20

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


Schedule of lectures (preliminary plan)

Lecture Date/Place Topic Slides Supplementary material
1 Tuesday, 08 October
11:00 - 13:00
Seminarraum FAV EG C
General Information,
short recapitulation of block 1 of the lecture
Formale Methoden der Informatik (185.291)
cc01, 4x1
cc02, 4x1
Thursday, 10 October
09:00 - 11:00
EI 5 Hochenegg HS
Quiz, first attempt


2 Tuesday, 15 October
11:00 - 13:00
Seminarraum FAV EG C
Logarithmic Space
cc03, 4x1 [Pap94] Chap. 7, 8
Thursday, 17 October
09:00 - 11:00
EI 5 Hochenegg HS
Quiz, second attempt


3 Monday, 21 October
11:00 - 13:00
Seminarraum FAV 01 B
Logarithmic Space (continued)

4 Tuesday, 22 October
11:00 - 13:00
Seminarraum FAV EG C
Boolean Logic

Homework 1 (pdf, tex)
cc04, 4x1 [Pap94] Chap. 4, 9
28/29 October no class


5 Monday, 04 November
11:00 - 13:00
Seminarraum FAV 01 B
NP-Completeness
cc05, 4x1 [Pap94] Chap. 9
6 Tuesday, 05 November
11:00 - 13:00
Seminarraum FAV EG C
NP-Completeness (continued)
11/12 November no class


7 Monday, 18 November
11:00 - 13:00
Seminarraum FAV 01 B
Polynomial Hierarchy [Pap94] Chap. 17
8 Tuesday, 19 November
11:00 - 13:00
Seminarraum FAV EG C
Polynomial Hierarchy (continued)
9 Monday, 25 November
11:00 - 13:00
Seminarraum FAV 01 B
Polynomial Hierarchy (continued)
10 Tuesday, 26 November
11:00 - 13:00
Seminarraum FAV EG C
Complexity of Logic-Based Abduction [EG95]
11 Monday, 2 December
11:00 - 13:00
Seminarraum FAV 01 B
Complexity of Logic-Based Abduction (continued)
12 Tuesday, 3 December
11:00 - 13:00
Seminarraum FAV EG C
PSPACE [Pap94] Chap. 19
13 Monday, 9 December
11:00 - 13:00
Seminarraum FAV 01 B
PSPACE (continued)
14 Tuesday, 10 December
11:00 - 13:00
Seminarraum FAV EG C
Parameterized complextiy
15 Monday, 16 December
11:00 - 13:00
Seminarraum FAV 01 B
reserve

Assessment

Assessment will be based on the quiz at the beginning of the term, homework assignements, and an oral exam in the last week before the Christmas holidays. 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 23 October, 2019

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. Disclaimer / Datenschutzerklärung