UP AND THE LOW AND HIGH HIERARCHIES - A RELATIVIZED SEPARATION

The low and high hierarchies within NP were introduced by Schoning in order to classify sets in NP. It is not known whether the low and high hierarchies include all sets in NP. In this paper, using the circuit lower-bound techniques of Hastad and Ko, we construct an oracle set re lative to which UP contains a language that is not in any level of the low hierarchy and such that no language in UP is in any level of the high hierarchy. Thus, in order to prove that UP contains languages tha t are in the high hierarchy or that UP is contained in the low hierarc hy, it is necessary to use nonrelativizable proof techniques. Since it is known that UPA is low for PPA for all sets A, our result also show s that the interaction between UP and PP is crucial for the lowness of UP for PP; changing the base class to any level of the polynomial-tim e hierarchy destroys the lowness of UP.