Teaching W24/25
Contents
Computational complexity theory aims to classify computational problems according to the algorithmic resources required for their solution. Resources are for example time, space, nondeterminism, or randomness. A central role is played by the class P of problems solvable in polynomial time. The central problem is the P versus NP problem, one of the Clay institute's millenium problems of mathematics, and, according to Smale, one of the three greatest open problems of mathematics. The course offers an introduction to this problem and its surrounding theory.
Continuously updated lecture notes on StudIP.
Lectures
Tuesday 12:00-14:00 IM HS 12
Wednesday 12:00-14:00 JUR SR 147a
Exercises
Thursday 12:00-14:00 JUR SR 059
Literatur
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
This Pro-/Seminar concerns the theory of the Resolution calculus, the simplest of all propositional calculi. It plays a central role in computer science, in particular, automated theorem provers or SAT solvers are based on it.
A set of clauses is unsatisfiable if and only if there exists a Resolution refutation of it. The central topic of the Pro-/Seminar is to prove lower bounds on the length of such refutations.
The Pro-/Seminar addresses students with an elementary background in logic but this is not a requirement. It can also be used as a first contact with mathematical logic.
This is an advanced seminar joint with Tobias Kaiser. It offers research talks of the respective groups and their visitors. Advanced students who wish to deepen their knowledge in mathematical logic and/or complexity theory can give talks on jointly chosen and jointly elaborated topics.
Programme pdf
A Constraint Satisfaction Problem (CSP) asks to decide whether there is an assignment to given variables, ranging over a certain domain, that satisfies a given set of constraints. Equivalently, this asks for a homomorphism between given structures. A famous example is the satisfiability problem for the Boolean domain (SAT).
The story of CSPs started 50 years ago, and during the last 25 years CSPs play a prominent role throughout computer science. On the one hand, they allow to model a wide variety of combinatorial problems (in mathematics, computer science, artificial intelligence...) in a natural and faithful way. On the other hand, they come together with general algorithmic techniques for their solution, or general reasons for their computational hardness. These techniques are based on universal algebra.
The course offers an introduction to the algebraic approach to CSPs. Knowledge of universal algebra is not assumed but developed as needed. Knowledge of mathematical logic is also not assumed. But students should have a basic knowledge of computational complexity, e.g., on the level of Theoretical Computer Science II. The lecture is accompanied by exercises. The course is conducted in English and is aimed at Master students. Details are to be found on StudIP.
Share this page
