Generic separations

摘要

M. Blum and R. Impagliazzo (Proc. 28th IEEE Symposium on Foundations of Computer Science, pp. 118-126, 1987), using techniques of Hartmanis and Hemachandra (1991) and Rackoff (1982), showed that if P = NP then P(G) = NP(G)/spl cap/co-NP(G) = UP(G), where G is a generic oracle. They left open the question as to whether these collapses occur at higher levels of the polynomial-time hierarchy. We give a surprising negative answer to this question. We show that relative to any generic oracle G and for any k/spl ges/ 2, there exists a tally set in U/spl Deltasub ksup P/(G)/spl capspl Pisub ksup P/(G) but not in /spl Deltasub ksup P/(G). An immediate corollary is that generic oracles separate /spl Sigmasub ksup Pspl capspl Pisub ksup P/ and /spl Deltasub ksup P/. We also show that related results hold for type-2 complexity.