Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-035 | 27th March 1996 00:00

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.

ISSN 1433-8092 | Imprint