In 1987, Blum and Impagliazzo, using techniques of Hartmanis and Hemac
handra and Rackoff, showed that if P=NP then P(G)= NP(G) boolean AND c
oNP(G) = UP(G), where G is a generic oracle. They leave open the quest
ion as to whether these collapses occur at higher levels of the polyno
mial-time hierarchy, i.e., Delta(k)(p)(G)=Sigma(k)(p)(G) boolean AND(s
ic)n(k)(p)(G) = U Delta(k)(p)(G) for k greater than or equal to 2. Her
e we give a negative answer to these questions. In fact. we demonstrat
e that, relative to any generic oracle G and for every k greater than
or equal to 2, there exists a tally set in U Delta(k)(p)(G) boolean AN
D(sic)n(k)(p)(G) but not in Delta(k)(p)(G) by showing an exponential l
ower bound of a certain type of families of constant-depth circuits. A
n immediate corollary is that generic oracles separate Sigma(k)(p) boo
lean AND(sic)(k)(p) and Delta(k)(p). We also show that related results
hold for type-2 complexity. (C) 1996 Academic Press, Inc.