Structural Complexity I

1 Introduction.- 2 Basic Notions About Models of Computation.- 1.1 Introduction.- 1.2 Alphabets, Words, Sets, and Classes.- 1.3 Inclusion Modulo Finite Variants.- 1.4 Boolean Formulas.- 1.5 Models of Computation: Finite Automata.- 1.6 Models of Computation: Taring Machines.- 1.7 Models of Computation: Nondeterministic Turing Machines.- 1.8 Models of Computation: Oracle Turing Machines.- 1.9 Bibliographical Remarks.- 3 Time and Space Bounded Computations.- 2.1 Introduction.- 2.2 Orders of Magnitude.- 2.3 Running Time and Work Space of Turing Machines.- 2.4 Time and Space Constructibility.- 2.5 Bounding Resources: Basic Definitions and Relationships.- 2.6 Bibliographical Remarks.- 4 Central Complexity Classes.- 3.1 Introduction.- 3.2 Definitions, Properties, and Examples.- 3.3 Computing Functions: Invertibility and Honesty.- 3.4 Polynomial Time Many-one Reducibility.- 3.5 "Natural" NP-complete Sets.- 3.6 "Natural" PSPACE-complete Sets.- 3.7 Padding Arguments.- 3.8 Space Bounded Reducibility.- 3.9 Exercises.- 3.10 Bibliographical Remarks.- 5 Time Bounded Turing Reducibilities.- 4.1 Introduction.- 4.2 Polynomial Time Turing Reducibility: Relativized Classes.- 4.3 Tally and Sparse Sets in NP.- 4.4 Strong Nondeterministic Polynomial Time Reducibility.- 4.5 Self-Reducibility.- 4.6 Exercises.- 4.7 Bibliographical Remarks.- 6 Nonuniform Complexity.- 5.1 Introduction.- 5.2 Classes Defined by Advice Functions.- 5.3 Boolean Circuit Complexity.- 5.4 Turing Machines and Boolean Circuits.- 5.5 Polynomial Advice.- 5.6 Logarithmic Advice.- 5.7 Self-Producible Circuits.- 5.8 A Lower Bound to the Circuit Size of Boolean Functions.- 5.9 Other Nonuniform Complexity Measures.- 5.10 Exercises.- 5.11 Bibliographical Remarks.- 7 Probabilistic Algorithms.- 6.1 Introduction.- 6.2 TheProbabilistic Computational Model.- 6.3 Polynomial Time Probabilistic Classes.- 6.4 Bounded Error Probability.- 6.5 Nonuniform Properties of BPP.- 6.6 Zero Error Probability.- 6.7 Exercises.- 6.8 Bibliographical Remarks.- 8 Uniform Diagonalization.- 7.1 Introduction.- 7.2 Presentability and Other Properties.- 7.3 The Main Theorem.- 7.4 Applications.- 7.5 Exercises.- 7.6 Bibliographical Remarks.- 9 The Polynomial Time Hierarchy.- 8.1 Introduction.- 8.2 Definition and Properties.- 8.3 Characterization and Consequences.- 8.4 Complete Sets and Presentability.- 8.5 BPP and the Polynomial Time Hierarchy.- 8.6 Exercises.- 8.7 Bibliographical Remarks.- References.- Appendix Complementation via Inductive Counting.- Author Index.- Symbol Index.