Foundations and Trends® in Theoretical Computer Science > Vol 2 > Issue 3

A Survey of Lower Bounds for Satisfiability and Related Problems

By Dieter van Melkebeek, University of Wisconsin, USA, dieter@cs.wisc.edu

 
Suggested Citation
Dieter van Melkebeek (2007), "A Survey of Lower Bounds for Satisfiability and Related Problems", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 2: No. 3, pp 197-303. http://dx.doi.org/10.1561/0400000012

Publication Date: 25 Oct 2007
© 2007 D. van Melkebeek
 
Subjects
Computational Models and Complexity
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
2 Preliminaries 
3 Common Structure of the Arguments 
4 Deterministic Algorithms 
5 Nondeterministic Algorithms 
6 Somewhat-Nonuniform Algorithms 
7 Randomized Algorithms 
8 Quantum Algorithms 
9 Future Directions 
Acknowledgments 
References 

Abstract

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 lineartime, 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.

DOI:10.1561/0400000012
ISBN: 978-1-60198-084-7
116 pp. $80.00
Buy book (pb)
 
ISBN: 978-1-60198-085-4
116 pp. $100.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
2: Preliminaries
3: Common Structure of the Arguments
4: Deterministic Algorithms
5: Nondeterministic Algorithms
6. Somewhat-Nonuniform Algorithms
7. Randomized Algorithms
8. Quantum Algorithms
9. Future Directions
Acknowledgements
References

A Survey of Lower Bounds for Satisfiability and Related Problems

NP-completeness arguably forms the most pervasive concept from computer science as it captures the computational complexity of thousands of important problems from all branches of science and engineering. The P versus NP question asks whether these problems can be solved in polynomial time. A negative answer has been widely conjectured for a long time but, until recently, no concrete lower bounds were known on general models of computation. Satisfiability is the problem of deciding whether a given Boolean formula has at least one satisfying assignment. It is the first problem that was shown to be NP-complete, and is possibly the most commonly studied NP-complete problem, both for its theoretical properties and its applications in practice. A Survey of Lower Bounds for Satisfiability and Related Problems surveys the recently discovered lower bounds for the time and space complexity of satisfiability and closely related problems. It overviews the state-of-the-art results on general deterministic, randomized, and quantum models of computation, and presents the underlying arguments in a unified framework. A Survey of Lower Bounds for Satisfiability and Related Problems is an invaluable reference for professors and students doing research in complexity theory, or planning to do so.

 
TCS-012