- Authors: S. Diehl and D. van Melkebeek.

- Reference:
*SIAM Journal on Computing*, 36: 563-594, 2006.

- Earlier version:

#### Abstract

We establish the first polynomial-strength time-space lower bounds for
problems in the linear-time hierarchy on randomized machines with bounded
two-sided error.
We show that for any integer *k* > 1 and constant
*c* < *k*, there exists a positive constant *d* such that
QSAT_{k} cannot be computed by such machines in time
*n*^{c} and space *n*^{d}, where
QSAT_{k} denotes the problem of deciding the validity of a
Boolean first-order formula with at most *k*-1 quantifier alternations.
Moreover, *d* approaches 1/2 from below as *c*
approaches 1 from above for *k* = 2, and *d* approaches 1 from
below as *c* approaches 1 from above for *k* ≥ 3.
In fact, we establish the stronger result that for any constants
*a* ≤ 1 and *c* < 1 + (*k* - 1)*a*,
there exists a positive constant *d* such
that linear-time alternating machines using space *n*^{a}
and *k*-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 *k* = 2, and *d* approaches *a*
from below as *c* approaches 1 from above for *k* ≥ 3.

Corresponding to *k* = 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.