This book makes my top-ten list of best computing books of the decade of the eighties. It certainly changed my outlook on how to write programs. The incorporation of logic into the code to mathematically prove that it works correctly was an ideal in the eighties and to some extent it remains an ideal. Nevertheless, that is not a reflection of the value of program correctness, but a consequence of the slow changes that sometimes take place in computing. Programmers may change their languages easily, but often not their styles.
CONTENTS
Preface
1. The Complexity of Computations
2. Time and Space Complexity Classes and Savitch’s Theorem
3. Separation Results
4. The Immerman–Szelepcs´enyi Theorem
5. Logspace Computability
6. The Circuit Value Problem
7. Alternation
8. Problems Complete for PSPACE
9. The Polynomial-Time Hierarchy
10. More on the Polynomial-Time Hierarchy
11. Parallel Complexity
12. Relation of NC to Time-Space Classes
13. Probabilistic Complexity
14. BPP ⊆ Σp
15. Interactive Proofs
16. PSPACE ⊆ IP
17. IP ⊆ PSPACE
18. Probabilistically Checkable Proofs
19. NP ⊆ PCP(n3,1)
20. More on PCP
21. Complexity of Decidable Theories
22. Complexity of the Theory of Real Addition
23. Lower Bound for the Theory of Real Addition
24. Lower Bound for Integer Addition
25. Automata on Infinite Strings and S1S
26. Determinization of ω-Automata
27. Safra’s Construction
28. Relativized Complexity
29. Nonexistence of Sparse Complete Sets
30. Circuit Lower Bounds and Relativized PSPACE = PH
31. Lower Bounds for Constant Depth Circuits
32. The Gap Theorem and Other Pathology
33. Partial Recursive Functions and G¨odel Numberings
34. Applications of the Recursion Theorem
35. The Arithmetic Hierarchy
36. Complete Problems in the Arithmetic Hierarchy
37. Post’s Problem
38. The Friedberg–Muchnik Theorem
39. The Analytic Hierarchy
40. Kleene’s Theorem
41. Fair Termination and Harel’s Theorem
Exercises
References
Notation and Abbreviations
Index
CONTENTS
Preface
1. The Complexity of Computations
2. Time and Space Complexity Classes and Savitch’s Theorem
3. Separation Results
4. The Immerman–Szelepcs´enyi Theorem
5. Logspace Computability
6. The Circuit Value Problem
7. Alternation
8. Problems Complete for PSPACE
9. The Polynomial-Time Hierarchy
10. More on the Polynomial-Time Hierarchy
11. Parallel Complexity
12. Relation of NC to Time-Space Classes
13. Probabilistic Complexity
14. BPP ⊆ Σp
15. Interactive Proofs
16. PSPACE ⊆ IP
17. IP ⊆ PSPACE
18. Probabilistically Checkable Proofs
19. NP ⊆ PCP(n3,1)
20. More on PCP
21. Complexity of Decidable Theories
22. Complexity of the Theory of Real Addition
23. Lower Bound for the Theory of Real Addition
24. Lower Bound for Integer Addition
25. Automata on Infinite Strings and S1S
26. Determinization of ω-Automata
27. Safra’s Construction
28. Relativized Complexity
29. Nonexistence of Sparse Complete Sets
30. Circuit Lower Bounds and Relativized PSPACE = PH
31. Lower Bounds for Constant Depth Circuits
32. The Gap Theorem and Other Pathology
33. Partial Recursive Functions and G¨odel Numberings
34. Applications of the Recursion Theorem
35. The Arithmetic Hierarchy
36. Complete Problems in the Arithmetic Hierarchy
37. Post’s Problem
38. The Friedberg–Muchnik Theorem
39. The Analytic Hierarchy
40. Kleene’s Theorem
41. Fair Termination and Harel’s Theorem
Exercises
References
Notation and Abbreviations
Index
Páginas : 403
Peso : 3mb.
Formato : PDF.
Edición : Primera
Año de Publicación :1987
ISBN : 978-0387964805
Editorial : Springer
Autor David Gries
0 comentarios:
Publicar un comentario