Theory of Computational Complexity / Edition 1

Theory of Computational Complexity / Edition 1

3.5 2
by Ding-Zhu Du, Ker-I Ko, Pre Athena Du
     
 

ISBN-10: 0471345067

ISBN-13: 9780471345060

Pub. Date: 01/27/2000

Publisher: Wiley

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

…  See more details below

Overview

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.

Read More

Product Details

ISBN-13:
9780471345060
Publisher:
Wiley
Publication date:
01/27/2000
Series:
Wiley Series in Discrete Mathematics and Optimization Series, #58
Pages:
512
Product dimensions:
6.40(w) x 9.59(h) x 1.12(d)

Related Subjects

Table of Contents

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.

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >

Theory of Computational Complexity 2 out of 5 based on 0 ratings. 1 reviews.
Guest More than 1 year ago
It is so unfortunate for me to use this book as a text. It is dense and hard to follow, without examples and explanations. Maybe it is good for experts, but I am sure it is not good for beginners.