Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
Scott R. Diehl, Dieter van Melkebeek · SIAM Journal on Computing · 2006
We establish the first polynomial‐strength time‐space lower bounds for problems in the linear‐time hierarchy on randomized machines with two‐sided error. We show that for any integer $\ell > 1$ and constant $c < \ell$, there exists a positive constant d such that QSAT$_{\ell}$ cannot be computed by such machines in time $n^c$ and space $n^d$, where QSAT$_{\ell}$ denotes the problem of deciding the validity of a quantified Boolean formula with at most $\ell - 1$ quantifier alternations. Moreover, d approaches 1/2 from below as c approaches 1 from above for $\ell = 2$, and d approaches 1 from below as c approaches 1 from above for $\ell \ge 3$. In fact, we establish the stronger result that for any constants $a \le 1$ and $c < 1 + (\ell - 1)a$, there exists a positive constant d such that linear‐time alternating machines using space $n^a$ and $\ell - 1$ alternations cannot be simulated by randomized machines with two‐sided error running in time $n^c$ and space $n^d$, where d approaches $a/2$ from below as c approaches 1 from above for $\ell = 2$, and d approaches a from below as c approaches 1 from above for $\ell \ge 3$. Corresponding to $\ell = 1$, we prove that there exists a positive constant d such that the set of Boolean tautologies cannot be decided by a randomized machine with one‐sided error in time $n^{1.759}$ and space $n^d$. As a corollary, this gives the same lower bound for satisfiability on deterministic machines, improving on the previously best known such result.