This is the first volume of a two volume textbook on structural complexity – a field of very active research in the last years. The main subjects of structural complexity theory are the complexity classes of time, space and other measures on different machine models and their relationships. Thus after an introduction chapters 2, 3 and 4 describe time and space bounded computations and central complexity classes together with the concept of reducibility and suitable properties of reductions as e.g. time bounds on Turing reducibility, completeness, honesty, invertibility of functions, paddability, self-reducibility.
Chapter 5 discusses circuits and nonuniform complexity, and chapter 6 describes the various concepts of probabilistic computation and complexity. Chapter 7 presents the powerful technique of uniform diagonalization. Chapter 8 describes some properties of the polynomial time hierarchy.
In an appendix the Immerman-Szelepcsényi result that non-deterministic space classes are closed under complement is shown by describing their counting technique (in the first edition of this textbook this still was mentioned as an open problem). The textbook has become a standard source for introductory courses on structural complexity at universities.