paper_8581

Department of Computer Science

Chair V

	University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1992	Copyright 1992 University of Bonn, Department of Computer Science, Abt. V
8581	On Randomized Versus Deterministic Computation Marek Karpinski, Rutger Verbeek [Download PostScript] [Download PDF] In contrast to deterministic or nondeterministic computation, it is a fundamental open problem in randomized computation how to separate different randomized time classes (at this point we do not even know how to separate linear randomized time from O(n^{log n}) randomized time) or how to compare them relative to corresponding deterministic time classes. In another words we are far from understanding the power of random coin tosses in the computation, and the possible ways of simulating them deterministically. In this paper we study the relative power of linear and polynomial randomized time compared with exponential deterministic time. Surprisingly, we are able to construct an oracle A such that exponential time (with or without the oracle A) is simulated by linear time Las Vegas algorithms using the oracle A. For Las Vegas polynomial time (ZPP) this will mean the following equalities of the time classes: ZPP^A = EXPTIME^A = EXPTIME(= DTIME(2^poly)).Furthermore, for all the sets M \subseteq \Sigma^* : M <_UR \bar{A} \Longleftrightarrow M \in EXPTIME(<_UR being unfaithful polynomial random reduction, c.f. [Jo 90]). Thus \bar{A} is <_UR complete for EXPTIME, but interestingly not NP-hard under (deterministic) polynomial reduction unless EXPTIME=NEXPTIME. We are also able to prove, for the first time, that randomized reductions are exponentially more powerful than deterministic or nondeterministic ones (cf. [AM 77]). Moreover, a set B is constructed such that Monte Carlo polynomial time (BPP) under the oracle B is exponentially more powerful than deterministic time with nondeterministic oracles, more precisely:BPP^B = \Delta₂EXPTIME^B = \Delta₂EXPTIME (= DTIME(2^poly)^NTIME(n)).This strengthens considerably a result of Stockmeyer [St 85] about the polynomial time hierarchy that for some decidable oracle B, BPP^B \not\subseteq \Delta₂P^B. Under our oracle BPP^B is exponentially more powerful than \Delta₂P^B, and B does not add any power to \Delta₂EXPTIME.
Last Change: 11/05/14 at 09:43:09 Deutsch	University of Bonn -> Department of Computer Science -> Chair V