Since the achievement of a fonnal definition of the concept of "algorithm", the Mathematical Theory of Computation has developed into a broad and rich discipline. The notion of "complexity of an algorithm" yields an important area of research, known as Complexity Theory, that can be approached from several points of view. Some of these are briefly discussed in the Introduction and, in particular, our view of the "Structural" approach is outlined there. We feel the subject is mature enough to permit collecting and interrelating many of the results in book fonn. Let us point out that a substantial part of the knowledge in Structural Complexity Theory can be found only in specialized journals, symposia proceedings, and monographs like doctoral dissertations or similar texts, mostly unpublished. We believe that a task to be done soon is a systematization of the interconnections between all the research lines; this is a serious and long task. We hope that the two volumes of this book can serve as a starting point for this systematization process.

Inhalt

1 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: Turing Machines.- 1.7 Models of Computation: Nondeterministic Turing Machines.- 1.8 Models of Computation: Oracle Turing Machines.- 1.9 Bibliographical Remarks.- 2 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.- 3 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.- 4 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.- 5 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.- 6 Probabilistic Algorithms.- 6.1 Introduction.- 6.2 The Probabilistic 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.- 7 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.- 8 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.- Author Index.- Symbol Index.