Overview
- Presents a broad view of the field covering all the fundamentals needed to study current research papers Introduces methods and results out of all main subareas.
- Extensive discussion of the literature at the end of each chapter Contains new material that has never before appeared in a textbook.
Part of the book series: Texts in Theoretical Computer Science. An EATCS Series (TTCS)
Access this book
Tax calculation will be finalised at checkout
Other ways to access
Table of contents (7 chapters)
Keywords
About this book
It begins with efficient Boolean circuits for problems with high practical relevance, e.g., arithmetic operations, sorting, and transitive closure, then compares the computational model of Boolean circuits with other models such as Turing machines and parallel machines. Examination of the complexity of specific problems leads to the definition of complexity classes. The theory of circuit complexity classes is then thoroughly developed, including the theory of lower bounds and advanced topics such as connections to algebraic structures and to finite model theory.
Authors and Affiliations
Bibliographic Information
Book Title: Introduction to Circuit Complexity
Book Subtitle: A Uniform Approach
Authors: Heribert Vollmer
Series Title: Texts in Theoretical Computer Science. An EATCS Series
DOI: https://doi.org/10.1007/978-3-662-03927-4
Publisher: Springer Berlin, Heidelberg
-
eBook Packages: Springer Book Archive
Copyright Information: Springer-Verlag Berlin Heidelberg 1999
Hardcover ISBN: 978-3-540-64310-4Published: 23 June 1999
Softcover ISBN: 978-3-642-08398-3Published: 08 December 2010
eBook ISBN: 978-3-662-03927-4Published: 17 April 2013
Series ISSN: 1862-4499
Series E-ISSN: 1862-4502
Edition Number: 1
Number of Pages: XI, 272
Topics: Theory of Computation, Computation by Abstract Devices, Algorithm Analysis and Problem Complexity, Mathematical Logic and Formal Languages, Computational Mathematics and Numerical Analysis, Electronics and Microelectronics, Instrumentation