期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：automata, Communication complexity, computational and structural complexity, determinism, Las Vegas, nondeterminism
