Structural Complexity I

1. Front Matter

   Pages i-ix

   PDF

2. Introduction

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

   Pages 1-4

3. Basic Notions About Models of Computation

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

   Pages 5-33

4. Time and Space Bounded Computations

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

   Pages 34-55

5. Central Complexity Classes

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

   Pages 56-82

6. Time Bounded Turing Reducibilities

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

   Pages 83-98

7. Nonuniform Complexity

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

   Pages 99-129

8. Probabilistic Algorithms

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

   Pages 130-149

9. Uniform Diagonalization

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

   Pages 150-159

10. The Polynomial Time Hierarchy

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

    Pages 160-176

11. Back Matter

    Pages 177-191

    PDF

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.

• Alphabet
• Turing machine
• algorithms
• automata
• complexity
• complexity theory
• formal language
• structural complexity

• Facultat d’Informàtica, Universität Politècnica de Catalunya, Barcelona, Spain

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

Policies and ethics