Structural Complexity I

1. Front Matter

   Pages I-XIII

   PDF

2. Introduction

   • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

   Pages 1-5

3. Basic Notions About Models of Computation

   • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

   Pages 6-35

4. Time and Space Bounded Computations

   • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

   Pages 36-58

5. Central Complexity Classes

   • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

   Pages 59-86

6. Time Bounded Turing Reducibilities

   • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

   Pages 87-103

7. Nonuniform Complexity

   • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

   Pages 104-135

8. Probabilistic Algorithms

   • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

   Pages 136-156

9. Uniform Diagonalization

   • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

   Pages 157-167

10. The Polynomial Time Hierarchy

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró

    Pages 168-185

11. Back Matter

    Pages 186-210

    PDF

In the six years since the first edition of this book was published, the field of Structural Complexity has grown quite a bit. However, we are keeping this volume at the same basic level that it had in the first edition, and the only new result incorporated as an appendix is the closure under complementation of nondeterministic space classes, which in the previous edition was posed as an open problem. This result was already included in our Volume II, but we feel that due to the basic nature of the result, it belongs to this volume. There are of course other important results obtained during these last six years. However, as they belong to new areas opened in the field they are outside the scope of this fundamental volume. Other changes in this second edition are the update of some Bibliograph­ ical Remarks and references, correction of many mistakes and typos, and a renumbering of the definitions and results. Experience has shown us that this new numbering is a lot more friendly, and several readers have confirmed this opinion. For the sake of the reader of Volume II, where all references to Volume I follow the old numbering, we have included here a table indicating the new number corresponding to each of the old ones.

• Berechnungsmodelle
• Complexity Classes
• Komplexitätsklassen
• Models of Computation
• Probabilistic Algorithms
• Probabilistische Algorithmen
• Reduzierbarkeit
• Resource bounded complexity
• Resourcenbeschränkte Komplexität
• complexity
• complexity theory
• algorithm analysis and problem complexity

• Department of Software (LSI), Universitat Politècnica de Catalunya, Barcelona, Spain

  José Luis Balcázar, Josep Díaz, Joaquim Gabarró

Policies and ethics