Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. xiv, 601 p. EUR 41.95 (net); sFr 72.00; £29.50; $ 44.95 (2002).
The authors give a survey of the present research concerning the study of Boolean functions, formulas, circuits and propositional proof systems. The first three chapters are dedicated to Boolean functions and circuit lower and upper bounds. Chapter 4 deals with the threshold phenomenon for 3-SAT (conjunctive normal forms on
variables and 3 literals per clause). In Chapter 5 several propositional proof systems are studied which have relevance to complexity theory: Gentzen calculus, resolution, algebraic refutation systems, Frege systems. Various computational models (uniform circuit families, Turing machines, parallel random access machines) are given in Chapter 6 and some features of parallel computation are illustrated by giving example programs. The last chapter includes an interesting study of the higher type functional complexity theory. Several open problems are presented.