Enhanced descriptions from Syndetics:

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.

Table of contents provided by Syndetics

• I Algorithms
• 1 Problems and Algorithms
• 2 Turing Machines
• 3 Undecidability
• II Logic
• 1 Boolean Logic
• 2 First Order Logic
• 3 Undecidability in Logic
• III P and NP
• 1 Relations between Complexity Classes
• 2 Reductions and Completeness
• 3 NP-Complete Problems
• 4 coNP and Function Problems
• 5 Randomized Computation
• 6 Cryptography
• 7 Approximability
• 8 On P vs. NP
• IV Inside P
• 1 Parallel Computation
• 2 Logarithmic Space
• V Beyond NP
• 1 The Polynomial Hierarchy
• 2 Computation That Counts
• 3 Polynomial Space
• 4 A Glimpse Beyond