Probabilistic Type-2 Operators and "Almost"-Classes

We define and examine several probabilistic operators rangi ng over sets (i.e., op- erators of type 2), among them the formerly studied ALMOST-operator. We compare their power and prove that they all coincide for a wide variet y of classes. As a con- sequence, we characterize the ALMOST-operator which ranges over infinite objects (sets) by a bounded-error probabilistic operator which ran ges over strings, i.e. finite objects. This leads to a number of consequences about complexity classes of cur- rent interest. As applications, we obtain (a) a criterion fo r measure 1 inclusions of complexity classes, (b) a criterion for inclusions of compl exity classes relative to a random oracle, (c) a new upper time bound for ALMOST-PSPACE,and (d) a char- acterization of ALMOST-PSPACE in terms of checking stack automata. Finally, a connection between the power of ALMOST-PSPACE and that of probabilistic circuits is given.