STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP

Recently, boolean hierarchies over NP and over RP (denoted BH and RBH respectively) have been introduced in complexity theory. They have proved particularly useful in carefully classifying natural problems which are not finely classified using more standard time and space complexity classes. In this paper we are particularly interested in the structural properties of these hierarchies and in relationships among various boolean hierarchies. Establishing the most significant relationships between BH, RBH, and other complexity classes would imply solving some of the major open problems in complexity theory. To date the only significant relations known are: , and RBH⊆BH. Essentially nothing is known about the fine structure of BH or of RBH. In [5] an oracle X is constructed for which both BHx and RBHx have an infinite number of proper levels. Further each level of RBH is properly contained in the corresponding level of BH, and RBH is properly contained in PP. In this paper we further explore these constructions. We prove that some of these separations are “strong” separations. That is, they can be witnessed by sets that cannot be “approximated” by sets in the smaller class: the separating sets are immune to sets from the smaller class. Specifically, we prove that the separations between RBH, BPP, PP and each level of BH, can be witnessed by immune sets.