Distinguished Lecturer Series (Computer Science)

Uwe Schöning (Ulm University) gives an invited lecture on „Algorithmen für das Erfüllbarkeitsproblem SAT“.

More information on the lecture and a general overview on the Distinguished Lecturer Series is available by following this link.

Abstract

Das SAT-Problem ist das erste, von dem die NP-Vollständigkeit nachgewiesen werden konnte, ebenso von dem eingeschränkten Problem 3SAT. Trotz NP-Vollständiglkeit zeigt sich, dass so genannte SAT-Solver in vielen Fällen Instanzen des SAT-Problem mit Tausenden von Variablen effizient lösen können. Es werden verschiedene Arten von SAT-Algorithmen besprochen, sowohl Backtracking-basierte als auch solche, die mit lokaler Suche arbeiten.