Abstract:
The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory. This paper continues in the comparison of the computational power of LasVegas computations with the computational power of deterministic and nondeterministic ones. While for one-way finite automata the comparison of different computational modes was successfully determined one does not have any nontrivial result relating the powers of determinism, Las Vegas and nondeterminism for two-way finite automata. The four main results of this paper are the following ones: 1, If, for a regular language L, there exist small two-way nondeterministic finite automata for both L and the complement of L, then there exists a small two-way Las Vegas finite automaton for L. 2, There is a quadratic gap between nondeterminism and LasVegas for the size of two-way finite automata. 3, There is an almost quadratic gap between Las Vegas and determinism for the size of two-way finite automata. 4, Two-way Las Vegas finite automata can be much more powerful than one-way nondeterministic finite automata. A consequence is an exponential gap between one-way Las Vegas finite automata and two-way Las Vegas finite automata.