Abstract:
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 ${\mathcal O}(n^{\log n})$ randomized time) or how to compare them relative to corresponding deterministic time classes. In other words we are far from understanding the power of {\em 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$.