Separating classes in the exponential-time hierarchy from classes in PH

AbstractWe are interested in separating classes in the exponential-time hierarchy, EXPH, from classes in the polynomial-time hierarchy, PH. In this paper we show that, for any fixed integer c, the class of sets accepted in deterministic polynomial time using at most O(nc) queries to an NP oracle, PNP[O(nc)], is a proper subset of NEXP. This improves a previous result by Fu et al. [7]. Further, we generalize this separation to related levels of PH and EXPH showing that, for any fixed integer c and i ⩾ 1, ΔiP[O(nc)] ⊊ ∑i − 1EXP. This improves the long standing separations which result from the relativization of the time hierarchy theorem [9, 6, 17, 3, 1]