Enhanced descriptions from Syndetics:

A complete treatment of fundamentals and recent advances in complexity theory Complexity theory studies the inherent difficulties of solving algorithmic problems by digital computers. This comprehensive work discusses the major topics in complexity theory, including fundamental topics as well as recent breakthroughs not previously available in book form. Theory of Computational Complexity offers a thorough presentation of the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization, and the application to cryptography. It also examines the theory of nonuniform computational complexity, including the computational models of decision trees and Boolean circuits, and the notion of polynomial-time isomorphism. The theory of probabilistic complexity, which studies complexity issues related to randomized computation as well as interactive proof systems and probabilistically checkable proofs, is also covered. Extraordinary in both its breadth and depth, this volume:
* Provides complete proofs of recent breakthroughs in complexity theory
* Presents results in well-defined form with complete proofs and numerous exercises
* Includes scores of graphs and figures to clarify difficult material
An invaluable resource for researchers as well as an important guide for graduate and advanced undergraduate students, Theory of Computational Complexity is destined to become the standard reference in the field.

Table of contents provided by Syndetics

• Uniform Complexity
• Models of Computation and Complexity Classes
• NP-Completeness
• The Polynomial-Time Hierarchy and Polynomial Space
• Structure of NP
• Nonuniform Complexity
• Decision Trees
• Circuit Complexity
• Polynomial-Time Isomorphism
• Probabilistic Complexity
• Probabilistic Machines and Complexity Classes
• Complexity of Counting
• Interactive Proof Systems
• Probabilistically Checkable Proofs andNP-Hard Optimization Problems
• Bibliography
• Index

Reviews provided by Syndetics

CHOICE Review

The modern theory of computational complexity began about 30 years ago with Cook's theorem, which provides the groundwork for showing the equivalence, in a certain precise sense, of hundreds of seemingly unrelated problems that resist efficient solution on a computer: an efficient solution of one gives an efficient solution for all. The theory now offers a fine-grained classification of computational problems according to the resources required for their solution--time, space, circuit structure, randomness, interaction, etc. Unfortunately, the ultimate shape of the classification rests on a host of recalcitrant conjectures. With the subject so new and moving so fast, just a few intrepid authors have attempted comprehensive works, notably the pioneering Computers and Intractability (1979) by Michael R. Garey and David S. Johnson; Computational Complexity (1994) by Christos H. Papadimitriou; and Introduction to the Theory of Computation (1997) by Michael Sipser. Here one finds both a basic introduction and comprehensive treatments, especially of topics that have borne spectacular fruit in just the last few years: circuit complexity, probabilistic complexity, interactive proof systems, probabilistically checkable proofs, and nonapproximability. Graduate students in this area of computer science will simply find this book indispensable. Upper-division undergraduates contemplating advanced study of this subject can look here for an accurate picture of the field's current flavor. D. V. Feldman University of New Hampshire

Author notes provided by Syndetics

DING-ZHU DU, PhD, is a professor in the Department of Computer Science at the University of Minnesota. KER-I KO, PhD, is a professor in the Department of Computer Science at the State University of New York at Stony Brook.