This text offers a comprehensive and accessible treatment of the
theory of algorithms and complexity - the elegant body of concepts and
methods developed by computer scientists over the past 30 years for
studying the performance and limitations of computer algorithms. Among
topics covered are: reductions and NP-completeness, cryptography and
protocols, randomized algorithms, and approximability of optimization
problems, circuit complexity, the "structural" aspects of the P=NP
question, parallel computation, the polynomial hierarchy, and many
others. Several sophisticated and recent results are presented in a
rather simple way, while many more are developed in the form of
extensive notes, problems, and hints. The book is surprisingly
self-contained, in that it develops all necessary mathematical
prerequisites from such diverse fields as computability, logic, number
theory, combinatorics and probability.
1. Problems and Algorithms.
LOGIC. 1. Boolean Logic.
3. Undecidability in Logic.
III. P AND NP. 1. Relations between
2. Reductions and
3. NP-Complete Problems.
4. coNP and Function Problems.
8. On P vs. NP.
IV. INSIDE P. 1. Parallel Computation.
2. Logarithmic Space.
V. BEYOND NP.
1. The Polynomial Hierarchy.
Computation That Counts.
3. Polynomial Space.
4. A Glimpse Beyond. 0201530821T04062001