
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 
NPCompleteness 
cc05, 4x1  [Pap94] Chap. 9 
6  Tuesday, 05 November 11:00  13:00 Seminarraum FAV EG C 
NPCompleteness (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 LogicBased Abduction  [EG95]  
11  Monday, 2 December 11:00  13:00 Seminarraum FAV 01 B 
Complexity of LogicBased 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 
Christos H. Papadimitriou: Computational Complexity. Addison Wesley, 1994. (Abbr. [Pap94])
Michael R. Garey, David S. Johnson: Computer and Intractability: A Guide to NPCompleteness. 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. 67161 (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):2729 (2003).
Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov: Complexity and Expressive Power of Logic Programming. ACM Computing Surveys 33(3):374425 (2001).
Thomas Eiter and Georg Gottlob: The Complexity of LogicBased Abduction. Journal of the ACM, 42(1):342 (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. 417422 (2007).
Oded Goldreich et al.: Introduction to Complexity Theory.
Last modified 23 October, 2019 