Using bounded query classes to separate classes in the exponential time hierarchy from classes in PH

摘要

We are interested in separating classes in the exponential time hierarchy, EXPH, from classes in the polynomial time hierarchy, PH. We show that for any fixed integer c, P/sup NP[O(n(c/)])/spl sube/NEXP. This improves a previous result by B. Fu, H. Li and Y. Zhong (1992). Further, we generalize this separation to related levels of PH and EXPH, showing that for any fixed integer c and i/spl ges/1, /spl Deltasub isup P[O(n(c/)])/spl subespl Sigmasub i-1sup EXP/. This improves the long standing separations which result from the relativization of the time hierarchy theorem. Related results for function classes are also considered.