The study of the computational power of randomized computations in one of the central tasks of complexity theory. The main aim of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. An at most polynomial gap has been established for the combinational complexity of circuits and for the communication complexity of two-party protocols. 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.
展开▼
