SAT Solving (WiSe 2026/27)

Praktikum, 4-std., Johannsen

Content

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(2^n) for brute-force search. The current best such (probabilistic) algorithms have a run-time of O(1.307^n) for 3-SAT and O(1.469^n) 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, in particular in hardware and software verification, in planning and combinatorial search.

The course will mainly treat these practical algorithms. The participants will first develop an application solving a puzzle by use of a state-of-the-art SAT solver. Then they will develop their own solver using the currently dominant CDCL paradigm.

Prerequisites

Knowledge of basic algorithmic techniques, as taught in the module Algorithmen und Datenstrukturen, and of the basics of computational complexity, as taught in the modules Formale Sprachen und Komplexität or Theoretische Informatik für Medieninformatiker, is required.

Organisation

The course will be held in English. The lecture and tutorial will take place in person at the time and place given below.

  • Umfang: 2+2 Semesterwochenstunden
  • Time and place:
    • Plenary: Tuesdays 14:15-15:45 (weekly)
    • Tutorial: Freitags 14:15-15:45 (on demand)
    • Both in room 101, Amalienstr. 73a
    • Changes in schedule due to organisational reasons:
      • The first two lectures will be on Tuesday, October 13 and Friday, October 16.
      • There will be no lecture on Tuesday, October 20.
      • The first tutorial will be on Tuesday, October 27.
  • Instructor: PD Dr. Jan Johannsen

Communication

There is an official chat-stream TCS-26W-SAT for the course at the institute's chat server, where the topics and organisation of the course can be discussed, and questions will be answered. This is my preferred channel of communication, therefore all participants are encouraged to subscribe to this channel.

Credits

There will be no oral or written exam. Instead, in order to obtain the credits for the course, the participants will have to successfully complete a number of small implementation projects specified in the problem sets. These projects are done in teams of 3 participants. After each due date, there will be an oral presentation and review of the projects. The first project will be issued in the first tutorial on October 27.

To top