GENERIC SEPARATIONS

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.