Inductive Time-Space Lower Bounds for Sat and Related Problems

We improve upon indirect diagonalization arguments for lower bounds on explicit problems within the polynomial hierarchy. Our contributions are summarized as follows. We present a technique that uniformly improves upon most known nonlinear time lower bounds for nondeterminism and alternating computation, on both subpolynomial (no(1)) space RAMs and sequential one-tape machines with random access to the input. We obtain improved lower bounds for Boolean satisfiability (SAT), as well as all NP-complete problems that have efficient reductions from SAT, and ∑k-SAT, for constant k ≥ 2. For example, SAT cannot be solved by random access machines using \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$n^{\sqrt{3}}$$ \end{document} time and subpolynomial space.We show how indirect diagonalization leads to time-space lower bounds for computation with bounded nondeterminism. For both the random access and multitape Turing machine models, we prove that for all k ≥ 1, there is a constant ck > 1 such that linear time with n1/k nondeterministic bits is not contained in deterministic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$n^{{c}_{k}}$$ \end{document} time with subpolynomial space. This is used to prove that satisfiability of Boolean circuits with n inputs and nk size cannot be solved by deterministic multitape Turing machines running in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $${n^{{k \cdot {c}}_{k}}}$$ \end{document} time and subpolynomial space.