__
TR05-137 | 21st November 2005 00:00
__

#### On Probabilistic Time versus Alternating Time

TR05-137
Authors:

Emanuele Viola
Publication: 28th November 2005 23:46

Downloads: 1683

Keywords:

alternating time,

approximate majority,

bottom fan-in,

BPP,

oracle,

PH,

probabilistic time,

quasilinear time,

time lower bound,

time-space tradeoff,

Turing machine
**Abstract:**
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.