TR97-029 Authors: Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

Publication: 21st August 1997 08:41

Downloads: 1075

Keywords:

The study of the computational power of randomized

computations is one of the central tasks of complexity theory. The

main goal of this paper is the comparison of the power of Las Vegas

computation and deterministic respectively nondeterministic

computation. We investigate the power of Las Vegas computation for the

complexity measures of one-way communication, finite automata and

polynomial-time relativized Turing machine computation.

(i) For the one-way communication complexity of two-party

protocols we show that Las Vegas communication can save at most one

half of the deterministic one-way communication complexity.

We also present a language for which this gap is tight.

(ii) For the size (i.e., the number of states) of finite

automata we show that the size of Las Vegas finite automata

recognizing a language $L$ is at least the root of the size of the

minimal deterministic finite automaton recognizing $L$. Using a

specific language we verify the optimality of this lower bound.

Note, that this result establishes for the first time an at most

polynomial gap between Las Vegas and determinism for a uniform

computing model.

(iii) For relativized polynomial computations we show that Las Vegas

can be even more powerful than nondeterminism with a polynomial

restriction on the number of nondeterministic guesses.

On the other hand superlogarithmic many advice bits in

nondeterministic computations can be more powerful than Las Vegas

(even Monte Carlo) computations in a relativized word.