- Author: D. van Melkebeek.
- Reference: In
G. Paun, G. Rozenberg, and A. Salomaa (eds.),
Current Trends in Theoretical Computer Science, pages 265-291,
World Scientific, 2004.
- Earlier version:
- D. van Melkebeek.
Time-Space Lower Bounds for
Satisfiability. In
Bulletin of the European Association for Theoretical
Computer Science, 73:57-77, 2001.
Abstract
We survey the recent lower bounds on the running time of
general-purpose random-access machines that solve satisfiability
in a small amount of work space, and related lower bounds for
satisfiability in nonuniform models. The same bounds apply to
almost all natural NP-complete problems known.
