Introduction to Circuit Complexity
A Uniform Approach
Published on 23. June 1999
Book
Hardback
XI, 272 pages
978-3-540-64310-4 (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
1999 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Lower undergraduate
Illustrations
XI, 272 p.
Dimensions
Height: 23.5 cm
Width: 15.5 cm
Weight
1290 gr
ISBN-13
978-3-540-64310-4 (9783540643104)
DOI
10.1007/978-3-662-03927-4
Schweitzer Classification
Other editions
Additional editions
Book
12/2010
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.