Time-Space Lower Bounds for NP-Complete Problems Download as PS


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.