Structural complexity II. (English) Zbl 0746.68032

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

EATCS Monographs on Theoretical Computer Science. 22. Berlin etc.: Springer-Verlag. IX, 283 p. (1990).

This second volume introduces several models for parallel computation and the corresponding complexity classes, the parallel computation thesis is then discussed.
Alternating turing machines (a special parallel model) is considered in Chapter 3. Chapter 4 introduces uniform circuit complexity, its relation to the models studied so far, and discusses the class NC.
Starting from Chapter 6, the book discusses several typical issues from structural complexity theory, such as the Berman-Hartmanis isomorphism conjecture and sparse sets; bi-immunity and complexity cores are considered in Chapter 6. Oracles and relativizational results (e.g. relativized separations and strong separations of \(P\) and \(NP\)) are presented in Chapter 7. Positive relativizations, i.e. oracle results that are conform with the absolute case are introduced in Chapter 8. In Chapter 9, the low hierarchy and the high hierarchy (as generalization of the \(NP\)-completeness notion) are considered that turn out to be useful in classifying \(NP\)-problems, but in a variant also problems outside \(NP\). Many of the previous results (e.g. on sparse sets) can be better understood and presented in more generality using (resource-bounded) Kolmogorov-complexity (Chapter 10). In Chapter 11, probabilistic complexity classes and interactive proof systems are considered (that can be used to characterize the graph isomorphism problem).
The appendix presents a proof of the Immerman/Szelepcsényi counting technique for complementing nondeterministic sparse classes.

Reviewer: U.Schöning (Ulm)

MSC:

68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68-02	Research exposition (monographs, survey articles) pertaining to computer science
68Q25	Analysis of algorithms and problem complexity
68Q30	Algorithmic information theory (Kolmogorov complexity, etc.)
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

computation models; complexity classes; structural complexity