Probabilistic Type-2 Operators and “Almost”-Classes

We define and examine several probabilistic operators ranging over sets (i.e., operators of type 2), among them the formerly studied ALMOST-operator. We compare their power and prove that they all coincide for a wide variety of classes. As a consequence, we characterize the ALMOST-operator which ranges over infinite objects (sets) by a bounded-error probabilistic operator which ranges over strings, i.e., finite objects. This leads to a number of consequences about complexity classes of current interest. As applications, we obtain (a) a criterion for measure 1 inclusions of complexity classes, (b) a criterion for inclusions of complexity classes relative to a random oracle, (c) a new upper time bound for ALMOST-PSPACE, and (d) a characterization of ALMOST-PSPACE in terms of checking stack automata. Finally, a connection between the power of ALMOST-PSPACE and that of probabilistic \( NC^1 \) circuits is given.

Authors and Affiliations

1. Department of Mathematics, University of California at Santa Barbara, Santa Barbara, CA 93106, USA, , , , , , US

   R.V. Book

2. Theoretische Informatik, Universität Würzburg, Am Exerzierplatz 3, D-97072 Würzburg, Germany, , , , , , DE

   H. Vollmer

3. Theoretische Informatik, Universität Würzburg, Am Exerzierplatz 3, D-97072 Würzburg, Germany, , , , , , DE

   K.W. Wagner

Received: 16 April 1996

Reprints and permissions