Time-space lower bounds for the polynomial-time hierarchy on randomized machines

摘要

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 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 quantified Boolean formula with at most l-1 quantifier alternations. Moreover, d approaches 1/2 from below as c approaches 1 from above for l = 2, and d approaches 1 from below as c approaches 1 from above for l >= 3. In fact, we establish the stronger result that for any constants a <= 1 and c < 1 + (l - 1) a, there exists a positive constant d such that linear-time alternating machines using space n(a) and l - 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 l = 2, and d approaches a from below as c approaches 1 from above for l >= 3. Corresponding to l = 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.