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.

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) |