Jetzt bewerten Jetzt bewerten
Bitte loggen Sie sich zunächst in Ihr Kundenkonto ein oder registrieren Sie sich bei
bücher.de, um das eBook-Abo tolino select nutzen zu können.
Hier
können Sie sich einloggen
Sie sind bereits eingeloggt. Klicken Sie auf 2. tolino select Abo, um fortzufahren.
Bitte loggen Sie sich zunächst in Ihr Kundenkonto ein oder registrieren Sie sich bei bücher.de, um das eBook-Abo tolino select nutzen zu können.
This volume II of a two-volume set assumes knowledge of the topics in Volume I but is otherwise nearly self-contained. Written at a graduate level, it includes numerous exercises and references.
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.
