Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-099 | 30th September 2007 00:00

A Survey of Lower Bounds for Satisfiability and Related Problems


Authors: Dieter van Melkebeek
Publication: 13th October 2007 15:17
Downloads: 2008


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 for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by Kannan, ruled out such an algorithm. Since then there has been a significant amount of progress giving non-trivial lower bounds on the computational complexity of satisfiability.

In this article we survey the known lower bounds for the time and space complexity of satisfiability and closely related problems on deterministic, randomized, and quantum models with random access. We discuss the state-of-the-art results and present the underlying arguments in a unified framework.

ISSN 1433-8092 | Imprint