Robustness of probabilistic computational complexity classes under definitional perturbations

Various types of probabilistic algorithms play an increasingly important role in computer science, especially in computational complexity theory. Probabilistic polynomial time complexity classes are defined and compared to each other, emphasizing some structural relationships to the known complexity classes P, NP, PSPACE. The classes R and ZPP, corresponding to the so-called Las Vegas polynomial time bounded algorithms, are given special attention. It is shown that many definitions, that arise naturally from different types of algorithms, are equivalent in defining the same class R (or ZPP, resp.). These robustness results justify finally the tractability of the above probabilistic classes