1985 · 554 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationAlgorithmic ComplexityBoolean AlgebraCircuit ComplexityComputational ComplexityComputational Complexity ClassesStructural ComplexityBoolean Circuit ComplexityCircuit Complexity Of Boolean FunctionsCircuit Lower BoundsCircuit Upper BoundsComplexity Of Boolean FunctionsLower BoundsPolynomial HierarchyPolynomial Time Complexity
We present exponential lower bounds on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct, i.e., ΣkP,A is properly contained in Σk+1P,A for all k.
17
Larry J. Stockmeyer · Theoretical Computer Science · 1976 · 1.3K citations
∑11-Formulae on finite structures
Miklós Ajtai · Annals of Pure and Applied Logic · 1983 · 586 citations