## A Survey of Lower Bounds for Satisfiability and Related ProblemsNP-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.

### 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 |

111 | |

### Common terms and phrases

apply argument Boolean formula bounds for satisﬁability Chapter circuits co-nondeterministic complexity classes conﬁguration coNT(nc contradiction with Lemma contradicts Lemma 3.1 counting hierarchy deﬁne denotes deterministic algorithms deterministic machines deterministic setting diﬀerent DTs(nd DTS(nd,ne DTs(t eliminate equivalent error that runs ﬁnish ﬁrst level ﬁxed Fortnow’s gate golden ratio guess bits iﬀ implies indirect diagonalization induction hypothesis latter Lemma linear logarithmic machine of type machine that runs machines with unbounded MajMajSAT MajSAT Master Theorem Melkebeek Mod2SAT nd and space nondeterministic algorithms nondeterministic computations nondeterministic machines nonnegative integer NP-complete NT(t one-sided error polylogarithmic polylogarithmic factors polynomial-time hierarchy positive real problems proof of Lemma Proposition 3.6 pseudorandom quantum algorithm quantum circuits quantum computations qubits random bits randomized algorithm randomized computations randomized machines real d sequence sorting networks space-bounded computations speedup step sublinear subpolynomial-space sufficiently large polynomial tape tautologies Theorem 1.3 time–space lower bounds transform two-sided error unbounded error values