Doctoral seminars

< back

Monday January 10 2005 at 14.00h in Celestijnenlaan 200A, room 3.14(cafetaria)

Lower Bounds for Satisfiability

by Dieter van Melkebeek

You are all cordially invited to this seminar.

Dieter van Melkebeek is an alumnus of our department (he graduated as a computer science engineer in 1991), and has built up a very succesful track record as a researcher in complexity theory. For his PhD dissertation on "Randomness and Completeness in Computational Complexity", he received the 1999 ACM Doctoral Dissertation Award.

Abstract:

Satisfiability is the problem of deciding whether a given propositional formula has a satisfying assignment. It constitutes the seminal NP-complete problem and is directly relevant to various branches of computer science. Complexity theorists widely believe that satisfiability takes exponential time in the worst case. However, they have been unable to rule out even the existence of a linear-time algorithm on general computation models with random access.

Recent years have seen a new approach to establish superlinear time lower bounds for satisfiability on random-access machines that use a small amount of space. For example, satisfiability cannot be solved on a random-access machine that runs in time n^c and subpolynomial space, where c denotes the golden ratio. The same bound applies to almost every natural NP-complete problem known.

This talk will survey the known lower bounds and give a flavor of the arguments involved.