Theory of Computational Complexity
Rights Contact Login For More Details
More About This Title Theory of Computational Complexity
English
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.
English
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 and NP-Hard Optimization Problems.
Bibliography.
Index.
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 and NP-Hard Optimization Problems.
Bibliography.
Index.
English
"Here one finds both a basic introduction and comprehensive treatments, especially of topics that have borne spectacular fruit in just the last few years..." (Choice, Vol. 38, No. 10, June 2001)
"Graduate students in this area of computer science will simply find htis book indispensable." (CHOICE, June 2001)
"Du and Ko present the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization..." (SciTech Book News, Vol. 24, No. 4, December 2000)
Overall, I would recommend this book as an excellent addition to the literature. (Bulleting of the London Mathematical Society, Volume 33, 2001)
"The book...is a graduate text...however, it can also be used profitably by researchers in theory...the selection by the authors of the book under review is excellent." (Mathematical Reviews, Issue 2001k)
Excerpt from publisher's description: "...promises to become the standard reference on computational complexity." (Zentralblatt MATH, Vol. 963, 2001/13)
"the book promises to become the standard reference on computational complexity" (Zentralblatt MATH, Vol.963, No.13 2001)
"Graduate students in this area of computer science will simply find htis book indispensable." (CHOICE, June 2001)
"Du and Ko present the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization..." (SciTech Book News, Vol. 24, No. 4, December 2000)
Overall, I would recommend this book as an excellent addition to the literature. (Bulleting of the London Mathematical Society, Volume 33, 2001)
"The book...is a graduate text...however, it can also be used profitably by researchers in theory...the selection by the authors of the book under review is excellent." (Mathematical Reviews, Issue 2001k)
Excerpt from publisher's description: "...promises to become the standard reference on computational complexity." (Zentralblatt MATH, Vol. 963, 2001/13)
"the book promises to become the standard reference on computational complexity" (Zentralblatt MATH, Vol.963, No.13 2001)
