Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR95-021 | 20th April 1995 00:00

#### On Randomized Versus Deterministic Computation

TR95-021
Authors: Marek Karpinski, Rutger Verbeek
Publication: 20th April 1995 16:12
Keywords:

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$.

ISSN 1433-8092 | Imprint