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