In the six years since the first edition of this book was published, the field of structural complexity has grown significantly. However, we are maintaining this volume at the same basic level as the first edition, and the only new result incorporated as an appendix is the closure under complementation of nondeterministic space classes, which was previously posed as an open problem. This result was already included in our Volume II, but we believe that due to its fundamental nature, it belongs in this volume. There are, of course, other important results obtained during these last six years. However, as they pertain to new areas opened in the field, they are outside the scope of this fundamental volume. Other changes in this second edition include updates to some bibliographical remarks and references, corrections of many mistakes and typos, and a renumbering of the sections.