Lecture  Date/Place  Topic  Slides  Supplementary material 
1  Tuesday, 07March 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, 09March 16:00  18:00 HS11 Paul Ludwik, Main Building 
Quiz, first attempt 


2  Tuesday, 14March 11:00  13:00 Seminarraum 188/2 
Logarithmic Space 
cc03, 4x1  [Pap94] Chap. 7, 8 
Thursday, 16March 16:00  18:00 HS11 Paul Ludwik, Main Building 
Quiz, second attempt 


Tuesday, 21March 
no class




3  Tuesday, 28March 11:00  13:00 Seminarraum 188/2 
Boolean Logic
Homework 1 (pdf, tex) 
cc04, 4x1  [Pap94] Chap. 4, 9 
4  Tuesday, 04April 11:00  13:00 Seminarraum 188/2 
Boolean Logic (continued)
Homework 2 (pdf, tex) 


5  Tuesday, 25April 11:00  13:00 Seminarraum 188/2 
NPCompleteness 
cc05, 4x1  [Pap94] Chap. 9 
6  Tuesday, 02May 11:00  13:00 Seminarraum 188/2 
Parameterized Complexity (Introduction)
Reading assignment 1 (pdf) 
sccc2013, 4x1  
7  Tuesday, 09May 11:00  13:00 Seminarraum 188/2 
Polynomial Hierarchy  cc06, 4x1  [Pap94] Chap. 17 
8  Tuesday, 16May 11:00  13:00 Seminarraum 188/2 
Polynomial Hierarchy (continued)
Homework 3 (pdf, tex) 


9  Tuesday, 23May 11:00  13:00 Seminarraum 188/2 
Polynomial Hierarchy (continued)
Homework 4 (pdf, tex) 

10  Tuesday, 30May 11:00  13:00 Seminarraum 188/2 
Complexity of LogicBased Abduction
Homework 5 (pdf, tex) 
cc07, 4x1  [EG95] 
Tuesday, 06June 
no class (pentecost holidays)




11  Tuesday, 13June 11:00  13:00 Seminarraum 188/2 
Complexity of LogicBased Abduction (continued)  
12  Tuesday, 20June 11:00  13:00 Seminarraum 188/2 
PSPACE  cc08, 4x1  [Pap94] Chap. 19 
13  Tuesday, 27June 11:00  13:00 Seminarraum 188/2 
PSPACE (continued)  
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 26 February, 2017 