A Survey of Lower Bounds for Satisfiability and Related Problems

Front Cover
Now Publishers Inc, 2007 - Computers - 114 pages
0 Reviews
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Selected pages

Contents

Introduction
1
11 Scope
12
12 Organization
14
Preliminaries
17
22 Complexity Classes
18
23 Complete Problems
22
Common Structure of the Arguments
29
31 Direct Diagonalization Results
31
42 Related Problems
55
Nondeterministic Algorithms
59
SomewhatNonuniform Algorithms
65
Randomized Algorithms
77
72 Related Problems
83
Quantum Algorithms
87
82 Connection with Quantum Algorithms
93
Future Directions
101

32 Speeding Up SpaceBounded Computations Using Alternations
34
33 Eliminating Alternations
39
34 A Concrete Example
40
Deterministic Algorithms
43
Acknowledgments
109
References
111
Copyright

Common terms and phrases

Bibliographic information