ON type-2 Probabilistic Quantifiers

摘要

We define and examine several probabilistic operators ranging over sets, among others the formerly studied ALMOST-operator. We compare their power and prove that they all coincide for a wide variety fo classes. As a consequence, we characterize the ALMOST-operator which ranges over infinite objects 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 oralce, (c) a new upper time bound for ALMOST-PSPACE, and (d) a characterization of ALMOST-PSPACE in terms fo checking stack automata. Finally, a connection between the power of ALMOST-PSPACE and that of probabilistic NC sup 1 circuits is given.