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 l > 1 and constant c < l, there exists a positive constant d such that QSAT_l cannot be computed by such machines in time n~c and space n~d, where QSAT_l denotes the problem of deciding the validity of a Boolean first-order formula with at most l - 1 quantifier alternations. Corresponding to l = 1, we prove that for any constant c < φ ≈ 1.618, 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~c and space n~d.
展开▼
