Structural Complexity I

This is the first of two volumes which present, in a systematic manner, the various areas of research in the field of structural complexity. Since the achievement of a formal 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. The present Volume I is written in a style appropriate for undergraduate students who have taken a first course in Formal Language Theory. The first two chapters of this volume present the basic concepts of structural complexity, providing the background necessary for the understanding of complexity theory. Volume II will be addressed to graduate students and researchers. Both volumes are written in a textbook style; they contain about 200 exercises. The readers are led to a point where very little additional work will enable them to start research projects. In order to ease this step, an effort has been made to point out the main references for each of the results presented in the text. 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 Front Matter....Pages i-ix Introduction....Pages 1-4 Basic Notions About Models of Computation....Pages 5-33 Time and Space Bounded Computations....Pages 34-55 Central Complexity Classes....Pages 56-82 Time Bounded Turing Reducibilities....Pages 83-98 Nonuniform Complexity....Pages 99-129 Probabilistic Algorithms....Pages 130-149 Uniform Diagonalization....Pages 150-159 The Polynomial Time Hierarchy....Pages 160-176 Back Matter....Pages 177-191 Introduction Basic Notions About Models of Computation Time and Space Bounded Computations Central Complexity Classes Time Bounded Turing Reducibilities Nonuniform Complexity Probabilistic Algorithms Uniform Diagonalization The Polynomial Time Hierarchy References Author Index Symbol Index Subject Index.