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


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)
cc01, 4x1
cc02, 4x1
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
cc03, 4x1 [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
Logarithmic Space (continued)
[Pap94] Chap. 4, 9
4 Tuesday, 10-April
11:00 - 13:00
Seminarraum 188/2
Boolean Logic
cc04, 4x1
5 Tuesday, 17-April
11:00 - 13:00
Seminarraum 188/2
Boolean Logic (continued)

6 Tuesday, 24-April
11:00 - 13:00
Seminarraum 188/2
NP-Completeness cc05, 4x1 [Pap94] Chap. 9
Tuesday, 01-May no class (public holiday)


Tuesday, 08-May no class due to the conferral of honorary doctorates
of TU Wien to Henry Fuchs and Moshe Vardi
in the main building, Böcklsaal (starting at 11:15)


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


8 Tuesday, 29-May
11:00 - 13:00
Seminarraum 188/2
Polynomial Hierarchy (continued)
9 Tuesday, 05-June
11:00 - 13:00
Seminarraum 188/2
Complexity of Logic-Based Abduction cc07, 4x1 [EG95]
Tuesday, 12-June no class


10 Tuesday, 19-June
11:00 - 13:00
Seminarraum 188/2
Complexity of Logic-Based Abduction (continued)
Thursday, 21-June
09:00 - 11:00
Seminarraum 183/2
Written exam
11 Tuesday, 26-June
11:00 - 13:00
Seminarraum 188/2
PSPACE [Pap94] Chap. 19
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

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