Introduction to circuit complexity. A uniform approach

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parallel algorithms in computer science (68W10) Analytic circuit theory (94C05)

Review text

The book presents a deep and thorough treatment of circuit complexity. Boolean circuits gain much of their attractiveness from the fact that nontrivial lower bounds for the complexity of particular practical problems in this model, are known. In the past few years, the study of complexity classes defined by Boolean circuits, as well as their properties and how they relate to other computational devices, has become more and more important. Best known are probably the classes that follow from the NC hierarchy, which was defined to capture the notion of problems that have very fast parallel algorithms using a feasible amount of hardware. This book is thus motivated from an algorithmic point of view, and therefore an important issue is the so-called uniformity of circuits, because only a uniform circuit family can be regarded as an implementation of an algorithm. The contents of the book is as follows. Chapter 1 starts examining a number of problems of highly practical relevance, such as basic arithmetic operations (addition, multiplication, division), counting, sorting, etc., from a circuit complexity viewpoint. The computation model of Boolean circuits and a construction of efficient circuits for these problems is formally developed. Chapter 2 compares the model of Boolean circuits with a number of other computation models, such as deterministic and alternating Turing machines and parallel random access machines. It is shown how these machines can simulate uniform circuit families, and, vice versa, how circuits can be constructed to simulate the computation of such machines. Chapter 3 considers the theory of lower bounds. All lower bounds given in this chapter will indeed hold for non-uniform circuits; e.g., it is shown that multiplication cannot even be computed by non-uniform circuits of a certain complexity. In Chapter 4 the class NC, a class of immense importance in the theory of parallel algorithms is examined. This class, in a sense, captures the notion of problems with very fast parallel algorithms using a feasible amount of hardware. Different aspects of the class NC and its structure are considered, and relations to diverse fields of mathematics such as group theory or finite model theory are studied. A further computation model, the so-called branching programs, will turn out to be important in this chapter. In Chapter 5 the author turns to circuits whose basic components are not logical gates but addition and multiplication gates. This study is thus not immediately motivated from a VLSI or engineering point of view, as is the case for Boolean circuits. The importance of this model stems from the fact that it serves as a theoretical basis for the field of computer algebra. In Chapter 6 higher classes are considered and it is shown how they relate to Boolean circuits. In the book the thorough mathematical presentation is complemented by many examples and exercises which allow the reader to better understand the subject.

Recommendations

Cited in

(only showing first 100 items - show all)

This page was built for publication: Introduction to circuit complexity. A uniform approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4393484)