### Generalized Lowness and Highness and Probabilistic Complexity Classes

Mathematical Systems Theory ** 22 ** (1989) 37-46.
Authors:

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science,
University of Kentucky, Lexington, KY, 40506-0046, klapper at cs.uky.edu.
www.cs.uky.edu/~klapper/andy.html

**Abstract**
We introduce generalized notions of low and high complexity classes and
study their relation to structural questions concerning bounded probabilistic
polynomial time complexity classes. We show, for example, that for a bounded
probabilistic polynomial time complexity class C = BP\Sigma^P_k, LC = HC
implies that the polynomial hierarchy collapses to C. This extends
Schoning's result for C = \Sigma^P_k (LC and HC are the low and high sets
defined by C.) We also show, with one exception, that containment relations
between the bounded probabilistic classes and the polynomial hierarchy are
preserved by their low and high counterparts. LBPP and LBPNP are characterized
as NP intersect BPP and NP intersect co-BPNP, respectively. These
characterizations are then used to recover of Boppana, Hastad, and Zachos's
result that if co-NP is a subset of BPNP, then the polynomial hierarchy
collapses to BPNP, and Ko's result that if NP is a subset of BPP, then the
polynomial hierarchy collapses to BPP.

**Index Terms --**
lowness, bounded probabilistic class, structural complexity theory,
polynomial hierarchy