Structural complexity II

From MaRDI portal





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.




Cited in
(95)








This page was built for publication: Structural complexity II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3996675)