Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-137 | 21st November 2005 00:00

On Probabilistic Time versus Alternating Time



We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) and BPTime(t) \subseteq \Sigma_c Time(t) for a large constant c > 3 (Ajtai, Adv. in Comp. Complexity Theory '93).

2) We prove that BPTime(t) \not \subseteq \Sigma_2 \Time(o(t^2)) with respect to some oracle.
This complements our result (1), and shows that the running time of the Sipser-Gacs-Lautemann simulation is optimal, up to a log(t) factor, for relativizing techniques. (All the results in (1) relativize.)

This result is obtained as a corollary from a new circuit lower bound for ``approximate majority'': poly(n)-size depth-3 circuits for approximate majority have bottom fan-in \Omega(log n).

3) We prove that solving QSAT_3 \in \Sigma_3 \Time(n polylog n) requires time n^{1 + \Omega(1)} on probabilistic Turing machines using space n^{.9}, with random access to input and work tapes, and two-way sequential access to the random-bit tape. This is the first lower bound of the form t = n^{1 + \Omega(1)} on a model with random access to the input and \emph{two-way} access to the random bits.

4) We prove that solving QSAT_3 \in \Sigma_3 Time(n polylog n) requires time n^{1 + \Omega(1)} on Turing machines with an input tape and a sequential work tape that is initialized with random bits. This is the first lower bound on a probabilistic extension of the two-tape off-line Turing machine model.

ISSN 1433-8092 | Imprint