Links und Funktionen

You are here: Home / Teaching / Winter 2015/16 / SAT Solving


SAT Solving

Lecture with Tutorial, 3+1 hours, Tu. 4-6pm, Th. 2-4pm, Johannsen


All questions answered on Thursday, Feb 04. Please send questions to Christian.


The satisfiability problem for classical propositional logic (SAT) is the canonical NP-complete problem, therefore algorithms for solving it are of essential importance for theoretical computer science, their development and study forms an entire area of research.

Recently there has been a lot of progress in this area, in theory as well as in practice. On the theoretical side, there are new algorithms for which worst-case upper bounds on the run-time can be proven, that are better than the obvious O(2n) for brute-force search. The current best such (probabilistic) algorithms have a run-time of O(1.308n) for 3-SAT and O(1.469n) for 4-SAT.

On the other hand, there are very good heuristics and implementations for the classic backtracking algorithms (DPLL), which can solve even very large inputs with hundred thousands of variables and millions of clauses in reasonably short time. These so-called SAT solvers have by now such a good performance that they are routinely used in applications for the solution of combinatorial optimization problems.

The course will treat these theoretical and practical algorithms, as well as some methods for proving lower bounds, and also some applications. The course will be held in English.


  • Umfang: 3+1 Semesterwochenstunden
  • Vorkenntnisse: Algorithmen und Datenstrukturen und Formale Sprachen und Komplexität bzw. Theoretische Informatik für Medieninformatiker
  • Vorlesung & Übung: Dr. Jan Johannsen, Christian Neukirchen


Die Vorlesung wird anerkannt:

  • für Studierende im Studiengang Informatik Master für das Modul Algorithmik und Komplexität
  • für Studierende im Studiengang Medieninformatik Master für das Modul Vertiefende Themen der Informatik für Master
  • für Studierende in den Studiengängen Informatik und Medieninformatik Bachelor für das Modul Vertiefende Themen der (Medien-) Informatik
  • für Studierende mit Nebenfach Informatik nach Vereinbarung

Time and Place

Lecture / Tutorial Di, 16-18 Uhr Raum 218 (Amalienstr. 73a)
Lecture Do, 14-16 Uhr Raum 220 (Amalienstr. 73a)


Lecture Slides


U. Schöning and J. Torán, The Satisfiability Problem: Algorithms and Analyses, Lehmans 2013, ISBN 978-3865415271


The tutorials will be held every two weeks in the Tuesday timeslot of the course, first on October 27.

Problem sets


To be announced



Document Actions