ECCC-Report TR95-021https://eccc.weizmann.ac.il/report/1995/021Comments and Revisions published for TR95-021en-usThu, 20 Apr 1995 16:12:18 +0300
Paper TR95-021
| On Randomized Versus Deterministic Computation |
Marek Karpinski,
Rutger Verbeek
https://eccc.weizmann.ac.il/report/1995/021In 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$.
Thu, 20 Apr 1995 16:12:18 +0300https://eccc.weizmann.ac.il/report/1995/021