Structural complexity. I. (English) Zbl 0638.68040

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

EATCS Monographs on Theoretical Computer Science, Vol. 11. Berlin etc.: Springer-Verlag. IX, 191 p., DM 54.00 (1988).

This is the first volume of a two volume textbook on a structurally oriented approach to complexity theory. Complexity theory is dealing with ressource-bounded universal computing devices, typically Turing machines. Structural complexity is interested in any interrelationship between complexity classes which is beyond the pure “quantitative” point of view. Many results in structural complexity theory are influenced by, or have their origin in, recursive function theory. The field has maturated in the last years and the present book is the first that summarizes and unifies many different contributions published up to now only in journal articles and conference proceedings.
After introducing the basic notions and computational models, discussing boundedness in resources such as time and space, many central structural issues are then presented in Chapters 3 and 4: reducibilities, completeness, honesty and invertibility of functions, paddability and self-reducibility of languages, and sparseness.
Chapter 5 introduces the concept of Boolean circuit (or nonuniform) complexity and compares it with the (uniform) notions discussed so far. The connection can be drawn via Karp and Lipton’s “advice” notion.
Probabilistic algorithms (and corresponding complexity classes) are the theme of Chapter 6. Such algorithms have achieved much attention in the last years. An interesting relation between probabilistic classes and the nonuniform classes from Chapter 5 is revealed in Section 6.5.
A uniform diagonalization method is then introduced in Chapter 7 which allows to obtain certain languages with “intermediate” properties. Finally, Chapter 8 finishes the book with a discussion of the polynomial time hierarchy - an analogue of Kleene’s arithmetical hierarchy - and again, another interesting link to the probabilistic classes is drawn in Section 8.5.
The book contains many exercises, both straightforward ones and some of a research project level. In most parts of the book the reader is led up to the current state of the art in research in the field. The list of references contains about 150 entries, so that every interested reader is invited (and gets a very good basis) for proceeding with his own research in the field.

Reviewer: U.Schöning

MSC:

68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68Q25	Analysis of algorithms and problem complexity
03D15	Complexity of computation (including implicit computational complexity)
03D10	Turing machines and related notions
68-02	Research exposition (monographs, survey articles) pertaining to computer science
03-02	Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations

Keywords:

bibliography; P-NP-problem; complete problems; structural properties; circuit complexity; diagonalization; complexity theory; Turing machines; complexity classes; structural complexity; Probabilistic algorithms; polynomial time hierarchy