Komplexitätstheorie

VU 181.142 (2.0) Sommersemester 2012

Reinhard Pichler

Table of Contents	News
General information Registration and Admission Course overview Schedule of lectures Assessment Books and further references	There will be only one reading assignment (with 10 credits maximum).

General informationen

Language. This lecture will most probably be held in English since it is part of the European Master's Program in Computational Logic (EMCL) curriculum.
Place. Classes will be held in the Seminarraum 188/2 (Favoritenstraße 9-11, 4th floor, stairs 3).
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, 16:00 - 18:00, HS11 Paul Ludwik, Main Building
- Thursday, 15 March, 16:00 - 18:00, HS11 Paul Ludwik, Main Building
This quiz is designed to ensure that students have the skills and knowledge taught in the introduction to complexity theory in the course Formale Methoden der Informatik.

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-Comleteness

In the first part of the Komplexitätstheorie lecture, these topics will be revisited and additional details will be provided such as

Logarithmic Space
Boolean Logic, proof of the Cook-Levin Theorem
More NP-Completeness

In the second part of the Komplexitätstheorie lecture, further topics will be touched on such as

The polynomial hierarchy
The class PSPACE
Applications (Database Theory, Abduction, ...)
Fixed-Parameter Tractability

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 - 19:00 HS11 Paul Ludwik, Main Building	Quiz, first attempt
2	Tuesday, 13-March 11:00 - 13:00 Seminarraum 188/2	Logarithmic Space Homework 1 (pdf, tex)	cc03, 4x1	[Pap94] Chap. 7, 8
	Thursday, 15-March 16:00 - 19:00 HS11 Paul Ludwik, Main Building	Quiz, second attempt
3	Tuesday, 20-March 11:00 - 13:00 Seminarraum 188/2	Boolean Logic	cc04, 4x1	[Pap94] Chap. 4, 9
4	Tuesday, 27-March 11:00 - 13:00 Seminarraum 188/2	Boolean Logic (continued) Homework 2 (pdf, tex)
	Tuesday, 17-April	no class
5	Tuesday, 24-April 11:00 - 13:00 Seminarraum 188/2	NP-Completeness	cc05, 4x1	[Pap94] Chap. 9
	Tuesday, 01-May	no class
6	Tuesday, 8-May 11:00 - 13:00 Seminarraum 188/2	NP-Completeness (continued) Reading Assignment (pdf, tex)
7	Tuesday, 15-May 11:00 - 13:00 Seminarraum 188/2	Polynomial Hierarchy	cc06, 4x1	[Pap94] Chap. 17
8	Tuesday, 22-May 11:00 - 13:00 Seminarraum 188/2	Polynomial Hierarchy (continued)
	Tuesday, 29-May	no class
9	Tuesday, 5-June 11:00 - 13:00 Seminarraum 188/2	Complexity of Logic-Based Abduction		[EG95]
10	Tuesday, 12-June 11:00 - 13:00 Seminarraum 188/2	PSPACE		[Pap94] Chap. 19
11	Tuesday, 19-June 11:00 - 13:00 Seminarraum 188/2	PSPACE (continued)
12	Tuesday, 26-June 11:00 - 13:00 Seminarraum 188/2	Treewidth

Assessment

Assessment will be based on the quiz at the beginning of the term, homework assignments, reading assignments and an 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 21 February, 2012