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.
Sprache
Verlagsort
Verlagsgruppe
Zielgruppe
Für höhere Schule und Studium
Maße
Höhe: 246 mm
Breite: 171 mm
Dicke: 30 mm
Gewicht
ISBN-13
978-0-201-53082-7 (9780201530827)
Schweitzer Klassifikation
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. 0201530821T04062001
