Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines Download as PS

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 QSATk cannot be computed by such machines in time nc and space nd, where QSATk 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 na and k-1 alternations cannot be simulated by randomized machines with two-sided error running in time nc and space nd, 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 n1.759 and space nd. As a corollary, this gives the same lower bound for satisfiability on deterministic machines, improving on the previously best known such result.

dieter@cs.wisc.edu