TR96-035 Authors: Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

Publication: 28th May 1996 09:10

Downloads: 2776

Keywords:

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.