go-v.orgdoi

A Survey of Lower Bounds for Satisfiability and Related Problems

Dieter van Melkebeek · Foundations and Trends® in Theoretical Computer Science · 2007

  • DOI 10.1561/0400000012
  • Publisher Now Publishers
  • Type article
  • Issued 2007

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

Foundations and Trends® in Theoretical Computer Science · Now Publishers · article · 2007

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

Open the resolved locator · 10.1561/0400000012

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 03:51 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1561/0400000012
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.