On the power of Las Vegas for one-way communication complexity, OBDDs, andfinite automata

The study of the computational power of randomized computations is one of t he central tasks of complexity theory. The main goal of this paper is the c omparison of the power of Las Vegas computation and deterministic respectiv ely nondeterministic computation. We investigate the power of Las Vegas com putation for the complexity measures of one-way communication, ordered bina ry decision diagrams, and finite automata. (i) For the one-way communication complexity of two-party protocols we show that Lis Vegas communication can save at most one half of the deterministi c one-way communication complexity. We also present a language for which th is gap is tight. (ii) The result (i) is applied to show an at most polynomial gap between de terminism and Las Vegas for ordered binary decision diagrams. (iii) 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 l east the square root of the size of the minimal deterministic finite automa ton recognizing L. Using a specific language we verify the optimality of th is lower bound. (C) 2001 Academic Press.