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.