[1] | D. Angluin, Counting problems and the polynomial-time hierarchy.Theoretical Computer Science, to appear. |

[2] | N. Blum, A 2.75n lower bound for the combinational complexity of boolean functions. University of Saarbrucken, Technical Report. |

[3] | T. Baker, J. Gill, and R. Solovay, Relativizations of theP =? NP question.SIAM Journal of Computing, 4, 4, 1975. |

[4] | T. Baker and A. Selman, A second step toward the polynomial hierarchy.Theoretical Computer Science, 8, 2, 1979, pp. 177–187. · Zbl 0397.03023 · doi:10.1016/0304-3975(79)90043-4 |

[5] | A. Chandra, D. Kozen, and L. Stockmeyer, Alternation.Journal of the ACM, 28, 1, January 1981. |

[6] | Digital Equipment Corporation,Decsystem 10 Assembly Language Handbook. Third Edition, 1973, pp. 51–52. |

[7] | M. Furst, Bounded width computation DAG’s. In preparation, 1982. |

[8] | M. Furst, J. B. Saxe, M. Sipser, Parity, circuits and the polynomial-time hierarchy. 22NDSymposium on the Foundations of Computer Science, 1981, pp. 260–270. |

[9] | M. Furst, J. B. Saxe, M. Sipser, Depth 3 circuits require ${\Omega}$(n clogn ) gates to compute parity: a geometric argument. In preparation. |

[10] | V. Krapchenko, Complexity of the realization of a linear function in the class of II-circuits. English translation inMath. Notes Acad. Sci., USSR, 1971, pp. 21–23; orig. inMat. Zamet, 9, 1, pp. 35–40. |

[11] | V. Krapchenko, A method of obtaining lower bounds for the complexity of II-schemes. English translation inMath. Notes Acad. Sci USSR, 1972, pp. 474–479; orig. inMat. Zamet, 10, 1, pp. 83–92. |

[12] | O. Lupanov, Implementing the algebra of logic functions in terms of constant-depth formulas in the basis +,*, -. English translation inSov. Phys.-Dokl., 6, 2, 1961; orig. inDokla. Akad. Nauk SSSR, 136, 5. |

[13] | R. Ladner and N. Lynch, Relativization of questions about log space computability.Mathematical Systems Theory, 10, 1, 1976. |

[14] | C. Mead and L. Conway,Introduction to VLSI Systems. Addison-Wesley, Reading, Mass. 1980. |

[15] | W. Paul, A 2.5N lower bound for the combinational complexity of boolean functions. 7thAnnual ACM Symposium on Theory of Computing, 1975, pp. 27–36. |

[16] | J. Savage,The Complexity of Computing. John Wiley and Sons, New York, 1976, Sect. 2.4. |

[17] | C. P. Schnorr, A 3n lower bound on the network complexity of boolean functions.Theoretical Computer Science, 10, 1, 1980, p. 83. · Zbl 0438.68012 · doi:10.1016/0304-3975(80)90074-2 |

[18] | L. J. Stockmeyer, The polynomial-time hierarchy.Theoretical Computer Science, 3, 1, 1976, pp. 1–22. · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X |

[19] | S. Skyum and L. G. Valiant, A complexity theory based on boolean algebra. 22ndSymposium on the Foundations of Computer Science, 1981, pp. 244–253. |

[20] | M. Sipser, On polynomial vs exponential growth. In preparation. |

[21] | L. Stockmeyer and A. Meyer, Word problems requiring exponential time, preliminary report. 5thAnnual ACM Symposium on Theory of Computing, 1973. |