ComputingComputer ScienceMathematicsAlgorithmsCircuit TheoryTheory Of ComputationAlgorithm AnalysisCircuit ComplexityComplexity TheoryComputational ComplexityTuring MachinesCircuit Lower BoundsCircuit Upper BoundsClosure PropertiesConstant-depth CircuitsLower BoundsPolynomial Time ComplexityPolynomial-time AlgorithmsUpper Bounds
The basic techniques for using polynomials in complexity theory are examined, emphasizing intuition at the expense of formality. The focus is on the connections to constant-depth circuits, at the expense of polynomial-time Turing machines. The closure properties, upper bounds, and lower bounds obtained by this approach are surveyed.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
48
Almost optimal lower bounds for small depth circuits
Johan Håstad · 1986 · 630 citations
Separating the polynomial-time hierarchy by oracles
Andrew Chi-Chih Yao · 1985 · 554 citations