ECCC-Report TR05-137https://eccc.weizmann.ac.il/report/2005/137Comments and Revisions published for TR05-137en-usMon, 28 Nov 2005 23:46:38 +0200
Paper TR05-137
| On Probabilistic Time versus Alternating Time |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2005/137We 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.
Mon, 28 Nov 2005 23:46:38 +0200https://eccc.weizmann.ac.il/report/2005/137