Algorithmen und Komplexität - Hauptseite Algorithmen und Komplexität

Oberseminar "Theoretische Informatik"

Beteiligte Lehrstühle

Das Oberseminar findet etwa einmal im Monat, an einem Freitag, im Raum 3.101 des Institutsgebäudes (Johann von Neumann-Haus, Rudower Chaussee 25) statt. Es werden Forschungsergebnisse aus der Theoretischen Informatik diskutiert.


aktuelle Termine

Termine des letzten Semesters

08.01.2008 Dieter van Melkebeek: Lower Bounds for Satisfiability and Related Problems

Zusammenfassungen

08.01.2008 Dieter van Melkebeek: Lower Bounds for Satisfiability and Related Problems

Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time logarithmic-space algorithm was not ruled out. Recent years have seen considerable progress in time-space lower bounds for satisfiability and closely related problems on deterministic, randomized, and quantum machines. This talk will survey the state-of-the-art and give a flavor of the arguments involved. Dieter van Melkebeek, University of Wisconsin


zuletzt geändert am 07.04.2005 (alkox-www)