zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Introduction to circuit complexity. A uniform approach. (English) Zbl 0931.68055
Texts in Theoretical Computer Science. Berlin: Springer. 300 p. DM 68.00; öS 497.00; sFr. 62.00 (1998).

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.


MSC:
68Q15Complexity classes of computation
68-01Textbooks (computer science)
94C05Analytic circuit theory
68W10Parallel algorithms