|
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 | |
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])
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).
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).
Oded Goldreich et al.: Introduction to Complexity Theory.
Last modified 18 February, 2018 |