
University of Bonn > Department of Computer Science > Chair V  
CSAPXReports 1992  Copyright 1992 University of Bonn, Department of Computer Science, Abt. V  
8912

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. Thus \bar{A} is <_{UR} complete for EXPTIME, but interestingly not NPhard 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: 

Last Change:
11/05/14 at 09:43:09
Deutsch 
University of Bonn > Department of Computer Science > Chair V 