Daniel Pierre Bovet, University of Rome, La Sapienza
Pierluigi Crescenzi

Published April, 1994 by Prentice Hall PTR (ECS Professional)

Copyright 1994, 330 pp.
Cloth
ISBN 0-13-915380-2
$50.00

Sign up for future
mailings on this subject.

See other books about:
    Models Of Computation

Using a balanced approach that is partly algorithmic and partly structuralist, this book systematically reviews the most significant results obtained in the study of computational complexity theory. KEY TOPICS: Considers properties of complexity classes, inclusions between classes, implications between several hypotheses about complexity classes, and identification of structural properties of sets that affect their computational complexity. Features over 120 worked examples, over 200 problems, and 400 figures. For those interested in complexity and computability, algorithm design, operations research, and combinational mathematic.

1. Mathematical Preliminaries.
2. Elements of Computability Theory.
3. Complexity Classes.
4. The Class P.
5. The Class NP.
6. The Complexity of Optimization Problems.
7. Beyond NP.
8. Space-Complexity Classes.
9. Probabilistic Algorithms and Complexity Classes.
10. Interactive Protocols.
11. Parallel Computation Models.
12. Parallel Algorithms.