Since a TUWEL course has been created for this lecture, the course homepage will no longer be maintained. 
Lecture  Date  Topic  Slides  Supplementary material 
1  Friday, 02 October 11:15  13:00 
General Information, short recapitulation of the lecture Formale Methoden der Informatik (185.291) 
cc01
cc02 

Tuesday, 06 October 09:00  11:00 
Quiz, first attempt 


2  Friday, 09 October 11:15  13:00 
Logarithmic Space 
[Pap94] Chap. 7, 8  
Tuesday, 13 October 09:00  11:00 
Quiz, second attempt 


3  Friday, 16 October 11:15  13:00 
Boolean Logic

[Pap94] Chap. 4, 9  
4  Friday, 23 October 11:15  13:00 
Boolean Logic (continued)



5  Friday, 30 October 11:15  13:00 
NPCompleteness 
[Pap94] Chap. 9  
6  Friday, 06 November 11:15  13:00 
NPCompleteness (continued)



7  Friday, 13 November 11:15  13:00 
Polynomial Hierarchy 

[Pap94] Chap. 17 
8  Friday, 20 November 11:15  13:00 
Polynomial Hierarchy (continued)  
9  Friday, 27 November 11:15  13:00 
Complexity of LogicBased Abduction  [EG95]  
10  Friday, 04 December 11:15  13:00 
Complexity of LogicBased Abduction (continued)  
11  Friday, 11 December 11:15  13:00 
PSPACE  [Pap94] Chap. 19  
Friday, 18 December 
no class




12  Friday, 08 January 11:15  13:00 
PSPACE (continued)  
13  Friday, 15 January 11:15  13:00 
Parameterized Complexity  
Tuesday, 19 January 09:00  11:00 
written exam  

14  Friday, 22 January 11:15  13:00 
discussion of written exam  

Tuesday, 26 January 09:00  12:00 
oral exam  
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 04 October, 2020 