Introduction to Circuit Complexity: A Uniform Approach

ISBN-13: 9783642083983 / Angielski / Miękka / 2010 / 272 str.

Heribert Vollmer

Opis

to Circuit COIllplexity A Uniform Approach With 29 Figures, Springer Author Dr. Heribert Vollmer Universitiit Wurzburg Theoretische Informatik Am Exerzierplatz 3 D-97072 Wurzburg, Germany vollmer@informatik. uni-wuerzburg. de Series Editors Prof. Dr. Wilfried Brauer Institut fUr Informatik, Technische Universitiit Munchen Arcisstrasse 21, D-80333 Munchen, Germany Prof. Dr. Grzegorz Rozenberg Department of Computer Science, University of Leiden Niels Bohrweg 1, P. O. Box 9512, 2300 RA Leiden, The Netherlands Prof. Dr. Arto Salomaa Data City, Turku Centre for Computer Science FIN-20520 Turku, Finland ISBN 978-3-642-08398-3 ACM Computing Classification (1998): F. l. l, F. 1. 3, F. 2. 0, F. 2. 3, FA. l, F. 4. 3 Library of Congress Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Vollmer;Heribert: Introduction to circuit complexity: a uniform approach / Heribert Vollmer. ISBN 978-3-642-08398-3 ISBN 978-3-662-03927-4 (eBook) DOI 10. 1007/978-3-662-03927-4 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concemed, specifica11y the rights of trans1ation, reprinting, reuse of illustrations, recitation. broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German copyright law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Berlin Heide1bergGmbH. Violations are liable for prosecution under the German Copyright Law.

Spis treści

1. Complexity Measures and Reductions.- 2. Relations to Other Computation Models.- 3. Lower Bounds.- 4. The NC Hierarchy.- 5. Arithmetic Circuits.- 6. Polynomial Time and Beyond.- Appendix: Mathematical Preliminaries.- A1 Alphabets, Words, Languages.- A2 Binary Encoding.- A3 Asymptotic Behavior of Functions.- A4 Turing Machines.- A5 Logic.- A6 Graphs.- A7 Numbers and Functions.- A8 Algebraic Structures.- A9 Linear Algebra.- List of Figures.- Author Index.

Blurb

This advanced textbook presents a broad and up-to-date view of the computational complexity theory of Boolean circuits. It combines the algorithmic and the computability-based approach, and includes extensive discussion of the literature to facilitate further study.
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.