## Du, Ding-Zhu

# Theory of Computational Complexity

Praise for the *First Edition*

"...complete, up-to-date coverage of computational complexity theory...the book promises to become the standard reference on computational complexity." -*Zentralblatt MATH*

A thorough revision based on advances in the field of computational complexity and readers’ feedback, the *Second Edition* of *Theory of Computational Complexity *presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered.

Maintaining extensive and detailed coverage, *Theory of Computational Complexity, Second Edition *examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The *Second Edition *also features recent developments on areas such as NP-completeness theory, as well as:

- A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science
- Additional exercises at varying levels of difficulty to further test comprehension of the presented material
- End-of-chapter literature reviews that summarize each topic and offer additional sources for further study

*Theory of Computational Complexity, Second Edition* is an excellent textbook for courses on computational theory and complexity at the graduate-level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.

**Keywords:** Chaos / Fractal / Dynamical Systems, Theory of Computational Complexity, Ding-Zhu Du, np-hard optimization, APX-hardness, (log n)-approximation, game conjecture, NP-completeness theory, nonuniform computational complexity, decision trees, Boolean circuits, PCP Theorems

- Author(s)
- Du, Ding-Zhu
- Ko, Ker-I
- Publisher
- John Wiley and Sons, Inc.
- Publication year
- 2014
- Language
- en
- Edition
- 2
- Series
- Wiley Series in Discrete Mathematics and Optimization
- Page amount
- 512 pages
- Category
- Natural Sciences
- Format
- Ebook
- eISBN (ePUB)
- 9781118594971
- Printed ISBN
- 9781118306086