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

Abstract

In this talk, we establish lower bounds for the running time of randomized
machines with two-sided error which use a small amount of workspace to
solve complete problems in the polynomial-time hierarchy.  In particular,
we show that for integers $l > 1$, a randomized machine with two-sided error
using subpolynomial space requires time $n^{l - o(1)}$ to solve QSATl, where
QSATl denotes the problem of deciding the validity of a Boolean first-order
formula with at most $l-1$ quantifier alternations. This represents the first
time-space lower bounds for complete problems in the polynomial-time
hierarchy on randomized machines with two-sided error.

Corresponding to $l = 1$, we show that a randomized machine with one-sided
error using subpolynomial space requires time $n^{1.759}$ to decide the set
of Boolean tautologies. As a corollary, this gives the same lower bound for
satisfiability on deterministic machines, improving on the previously best
known such result.