Komplexitätstheorie

VU 181.142 (2.0) Wintersemester 2020

Reinhard Pichler

Table of Contents	News
General information Registration and Admission Course overview Schedule of lectures Assessment Books and further references	Since a TUWEL course has been created for this lecture, the course homepage will no longer be maintained.

General information

Language. This lecture will most probably be held in English since it is part of the English master's programme in "Logic and Computation".
Place. Due to the Covid-19 situation, all classes will be held online via Zoom. The Zoom link is shown in TUWEL.
Time. The course has a regular meeting time. Classes will be held Fridays, 11:15 - 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 (185.291)". 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 (185.291).

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 (details to be announced in the first class). Each student has at most two attempts:
- Tuesday, 6 October 2020, 09:00 - 11:00
- Tuesday, 13 October 2020, 09:00 - 11:00
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 (185.291).

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

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

Turing Machines, Complexity Classes
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 (as time permits) such as

The polynomial hierarchy
The class PSPACE
Applications (Database Theory, Abduction, ...)
Parameterized Complexity

Schedule of lectures (preliminary plan)

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	NP-Completeness		[Pap94] Chap. 9
6	Friday, 06 November 11:15 - 13:00	NP-Completeness (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 Logic-Based Abduction		[EG95]
10	Friday, 04 December 11:15 - 13:00	Complexity of Logic-Based 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

Assessment

Assessment will be based on the quiz at the beginning of the term and a written exam as well as an oral 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 04 October, 2020