Introduction to Circuit Complexity
A Uniform Approach
Published on 8. December 2010
Book
Paperback/Softback
XI, 272 pages
978-3-642-08398-3 (ISBN)
Description
An advanced textbook giving a broad, modern view of the computational complexity theory of boolean circuits, with extensive references, for theoretical computer scientists and mathematicians.
More details
Series
Edition
Softcover reprint of hardcover 1st ed. 1999
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Lower undergraduate
Illustrations
XI, 272 p.
Dimensions
Height: 234 mm
Width: 156 mm
Thickness: 16 mm
Weight
442 gr
ISBN-13
978-3-642-08398-3 (9783642083983)
DOI
10.1007/978-3-662-03927-4
Schweitzer Classification
Other editions
Additional editions
Book
06/1999
Springer
€80.24
Shipment within 7-9 days
Content
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.