The complexity of Boolean functions. (English) Zbl 0623.94018

Wegener, Ingo

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č

MSC:

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)

Keywords:

computational complexity; Boolean formula; parallel computations; complexity of Boolean functions; computation models; Boolean circuits; minimization; combinational complexity; lower bound; circuit complexity; nonuniform complexity measures; Turing machines; monotone circuits; bounded-depth circuits; synchronous circuits; planar circuits; parallel random access machines; branching programs