Introduction
1. Vector Machines
1.1. Introduction
1.2. Vector Machines: Definition and Basic Properties
1.3. Elementary Matrix Algebra on Vector Machines
1.4. Relation Between Vector Machines and Turing Machines
1.5. Exercises
1.6. Bibliographical Remarks
2. The Parallel Computation Thesis
2.1. Introduction
2.2. An Array Machine: the APM
2.3. A Multiprocessor Machine: the SIMDAG
2.4. A Tree Machine: the k-PRAM
2.5. Further Parallel Models
2.6. Exercises
2.7. Bibliographical Remarks
3. Alternation
3.1. Introduction
3.2. Alternating Turing Machines
3.3. Complexity Classes for Alternation
3.4. Computation Graphs of a Deterministic Turing Machine
3.5. Determinism Versus Nondeterminism for Linear Time
3.6. Exercises
3.7. Bibliographical Remarks
4. Uniform Circuit Complexity
4.1. Introduction
4.2. Uniform Circuits: Basic Definitions
4.3. Relationship with General-Purpose Parallel Computers
4.4. Other Uniformity Conditions
4.5. Alternating Machines and Uniformity
4.6. Robustness of NC and Conclusions
4.7. Exercises
4.8. Bibliographical Remarks
5. Isomorphism and NP-completeness
5.1. Introduction
5.2. Polynomial Time Isomorphisms
5.3. Polynomial Cylinders
5.4. Sparse Complete Sets
5.5. Exercises
5.6. Bibliographical Remarks
6. Bi-Immunity and Complexity Cores
6.1. Introduction
6.2. Bi-Immunity, Complexity Cores, and Splitting
6.3. Bi-Immune Sets and Polynomial Time m-Reductions
6.4. Complexity Cores and Polynomial Time rn-Reductions
6.5. Levelability, Proper Cores, and Other Properties
6.6. Exercises
6.7. Bibliographical Remarks
7. Relativization
7.1. Introduction
7.2. Basic Results
7.3. Encoding Sets in NP Relativized
7.4. Relativizing Probabilistic Complexity Classes
7.5. Isolating the Crucial Parameters
7.6. Refining Nondeterminism
7.7. Strong Separations
7.8. Further Results in Relativizations
7.9. Exercises
7.10. Bibliographical Remarks
8. Positive Relativizations
8.1. Introduction
8.2. A Positive Relativization of the P = PSPACE Problem
8.3. A Positive Relativization of the NP = PSPACE Problem
8.4. A Positive Relativization of the P = NP Problem
8.5. A Relativizing Principle
8.6. Exercises
8.7. Bibliographical Remarks
9. The Low and the High Hierarchies
9.1. Introduction
9.2. Definitions and Characterizations
9.3. Relationship with the Polynomial Time Hierarchy
9.4. Some Classes of Low Sets
9.5. Oracle-Restricted Positive Relativizations
9.6. Lowness Outside NP
9.7. Exercises
9.8. Bibliographical Remarks
10. Resource-Bounded Kolmogorov Complexity
10.1. Introduction
10.2. Unbounded Kolmogorov Complexity
10.3. Resource-Bounded Kolmogorov Complexity
10.4. Tally Sets, Printability, and Ranking
10.5. Kolmogorov Complexity of Characteristic Functions
10.6. Exercises
10.7. Bibliographical Remarks
11. Probability Classes and Proof-Systems
11.1. Introduction
11.2. Interactive Proof-Systems: Basic Definitions and Examples
11.3. Arthur Against Merlin Games
11.4. Probabilistic Complexity Classes and Proof-Systems
11.5. Equivalence of AM and IP
11.6. Exercises
11.7. Bibliographical Remarks
Appendix: Complementation via Inductive Counting
1 Nondeterministic Space is Closed Under Complement
2 Bibliographical Remarks
References
Author Index
Symbol Index
Subject Index