Introduction to Circuit Complexity

TRAMA

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.

SOMMARIO

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.

ALTRE INFORMAZIONI

• Condizione: Nuovo
• ISBN: 9783540643104
• Collana: Texts in Theoretical Computer Science. An EATCS Series
• Dimensioni: 235 x 155 mm Ø 1290 gr
• Formato: Copertina rigida
• Illustration Notes: XI, 272 p.
• Pagine Arabe: 272
• Pagine Romane: xi