Introduction to the Theory of Complexity

Front Cover
Prentice Hall, 1994 - Mathematics - 282 pages
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.

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Elements of computability theory
12
Complexity classes
33
The class P
51
Copyright

10 other sections not shown

Common terms and phrases

About the author (1994)

Bovet has a Ph.D. in Computer Science from UCLA and is currently a full professor at the University of Rome, Italy.

Bibliographic information