Papadimitriou C.M. Computational Complexity

Издательство Addison-Wesley, 1994, -540 pp.
This book is an introduction to the theory of computational complexity at a level appropriate for a beginning graduate or advanced undergraduate course. Computational complexity is the area of computer science that contemplates the reasons why some problems are so hard to solve by computers. This field, virtually non-existent only 20 years ago, has expanded tremendously and now comprises a major part of the research activity in theoretical computer science. No book on complexity can be comprehensive now-certainly this one is not. It only contains results which I felt I could present clearly and relatively simply, and which I consider central to my point of view of complexity.
At the risk of burdening the reader so early with a message that will be heard rather frequently and loudly throughout the book's twenty chapters, my point of view is this: I see complexity as the intricate and exquisite interplay between computation (complexity classes) and applications (that is, problems). Completeness results are obviously central to this approach. So is logic, a most important application that happens to excel in expressing and capturing computation. Computation, problems, and logic are thus the three main currents that run through the book.Part I: Algorithms
Problems and Algorithms
Turing machines
Computability
Part II: Logic
Boolean logic
First-order logic
Undecidability in logic
Part III: P and NP
Relations between complexity classes
Reductions and completeness
NP-complete problems
coNP and function problems
Randomized computation
Cryptography
Approximability
On P vs. NP
Part IV: Inside P
Parallel computation
Logarithmic space
Part V: Beyond NP
The polynomial hierarchy
Computation that counts
Polynomial space
A glimpse beyond