Komplexitätstheorie
VU 181.142 (2.0) Sommersemester 2018
Reinhard Pichler
|
|
General information
- Language. This lecture will most probably be held in English since it is part of the English master's programme in "Logic and Computation".
- Place. Classes will be held in the Seminarraum 188/2 (Favoritenstraße 9-11, stairs 3, 4th floor).
- Time. The course has a regular meeting time. Classes will be held Tuesdays, 11:00 sharp - 13:00.
- Prerequisites. This course is designed for master's students. It is highly recommended to attend this course after the course Formale Methoden der Informatik (185.291). Students are assumed to have a basic knowledge in mathematical logic and to be familiar with basic concepts of complexity theory to the extent taught in the course "Formale Methoden der Informatik". Above all, students should have the skills and knowledge taught in the introduction to complexity theory in that course. In particular, students should have a clear understanding of the central concept of "problem reduction" and they should have no difficulty with the exercise sheet (block 1) of the course Formale Methoden der Informatik.
Registration and Admission
- Registration in TISS is required for this course!! (Attention: registration != subscription)
- Admission to the course requires positive assessment in a quiz at the beginning of the term. Each student has at most two attempts:
- Thursday, 8 March 2018, 16:00 - 18:00, HS11 Paul Ludwik, Main Building
- Thursday, 15 March 2018, 16:00 - 18:00, HS11 Paul Ludwik, Main Building
Course overview
The most fundamental notions and results of complexity theory have already been covered in the lecture Formale Methoden der Informatik (185.291):- Algorithms and Problems
- Turing machines
- Basic complexity classes (time/space, deterministic/non-deterministic)
- Undecidability
- Reductions, completeness
- NP-Completeness
- Logarithmic Space
- Boolean Logic, proof of the Cook-Levin Theorem
- More NP-Completeness
- The polynomial hierarchy
- The class PSPACE
- Applications (Database Theory, Abduction, ...)
- Parameterized Complexity
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 |