Better Time-Space Lower Bounds for SAT and Related Problems
Ryan Williams · 2005
We make several improvements on time lower bounds for concrete problems in NP and PH. 1) We present an elementary technique based on "indirect diagonalization" that uniformly improves upon the known nonlinear time lower bounds for nondeterminism and alternating computation, on both sublinear (n/sup o(1)/) space RAMs and sequential worktape machines with random access to the input. We obtain better lower bounds for SAT as well as all NP-complete problems that have efficient reductions from SAT and /spl Sigma//sub k/-SAT for constant k /spl ges/ 2. For example, SAT cannot be solved by random access machines using n/sup /spl radic/(3) /time and n/sub o(1)/ space. The technique is a natural inductive approach, for which previous work is essentially its base case. 2) We show how indirect diagonalization can also yield time-space lower bounds for computation with bounded nondeterminism. One corollary is that for all k, there exists a constant c/sub k/ > 1 such that satisfiability of Boolean circuits with n inputs and n/sup k/ gates cannot be solved in deterministic time n/sup k/spl middot/c//sub k/ and n/sup o(1)/ space.