Structural complexity II. (English) Zbl 0746.68032

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)


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)