Dieter van Melkebeek (Univ. of Wisconsin)
Sunday, 23.11.2008, 12:00
Ever since the work of Cook and Levin, 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.
The last few years have seen considerable progress in time-space lower
bounds for satisfiability and closely related problems on various
models of computation. This talk will describe the state-of-the-art on
deterministic, randomized, and quantum machines, survey the underlying
ideas, and present some of the arguments involved.