Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0931.68055
Vollmer, Heribert
Introduction to circuit complexity. A uniform approach. (English)
[B] Texts in Theoretical Computer Science. Berlin: Springer. 300 p. DM 68.00; öS 497.00; sFr. 62.00 (1998). ISBN 3-540-64310-9/hbk

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.\par 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.\par 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.\par 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.\par 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.\par 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.\par In Chapter 6 higher classes are considered and it is shown how they relate to Boolean circuits.\par In the book the thorough mathematical presentation is complemented by many examples and exercises which allow the reader to better understand the subject.
[Jacek Błazewicz (Poznań)]

MSC 2000:: *68Q15 Complexity classes of computation
68-01 Textbooks (computer science)
94C05 Analytic circuit theory
68W10 Parallel algorithms

Keywords: circuit complexity; Boolean circuits

Cited in: Zbl 1001.68050

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]