The complexity of Boolean functions. (English) Zbl 0623.94018

Wiley-Teubner Series in Computer Science. Stuttgart: B. G. Teubner; Chichester etc.: John Wiley & Sons. XI, 457 p.; DM 64.00 (1987).
An excellent monograph devoted to the complexity of Boolean functions is presented. It is the most complete work covering this area. Excluding the VLSI circuits all main computation models for Boolean functions are included. Both sources - English and Russian literature are used.
First, Boolean circuits as the basic model for the study of Boolean function complexities are considered. The essential concepts covering the minimization of Boolean functions, asymptotic (Shannon’s) characterization of combinational complexity, the design of efficient circuits for some fundamental functions, and lower bound techniques for circuit complexity are presented.
The nonuniform complexity measures - formula size and depth are considered and related to combinational complexity. Turing machines and other uniform computing models are related to combinational complexity, too. An overview concerning the study of special types of circuits (monotone circuits, bounded-depth circuits, synchronous circuits, planar circuits) is provided.
The last sections of this monograph are devoted to parallel random access machines and to branching programs which are among the mostly studied computing models in the last few years.
Reviewer: J.Hromkovič


94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
06E30 Boolean functions
03D15 Complexity of computation (including implicit computational complexity)