Structural Complexity II

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 m-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.7Strong 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 $$Pmathop = limits^? PSPACE$$ Problem.- 8.3 A Positive Relativization of the $$NPmathop = limits^? PSPACE$$ Problem.- 8.4 A Positive Relativization of the $$Pmathop = limits^? 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.