## Structural complexity IIThis is the second volume of a systematic two-volume presentation of the various areas of research in the field of structural complexity. The mathematical theory of computation has developed into a broad and rich discipline within which the theory of algorithmic complexity can be approached from several points of view. This volume is addressed to graduate students and researchers and assumes knowledge of the topics treated in the first volume but is otherwise nearly self-contained. Topics covered include vector machines, parallel computation, alternation, uniform circuit complexity, isomorphism, biimmunity and complexity cores, relativization and positive relativization, the low and high hierarchies, Kolmogorov complexity and probability classes. Numerous exercises and references are given. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

The Parallel Computation Thesis | 33 |

Alternation | 63 |

Copyright | |

12 other sections not shown

### Common terms and phrases

algorithm alternating machine alternating Turing machine Assume binary bits boolean chapter characterization co-NP complement complexity classes complexity core computation tree concept configuration consider constant construction Corollary defined Definition denote deterministic machine deterministic Turing machine diagonalization encoding Exercise existential exists fc-PRAM finite gate given global memory graph guess implies infinite input instruction isomorphic Kolmogorov complexity labeled language Lemma matrix node nondeterminism nondeterministic machine NP-complete NP(A NP(B number of queries obtain oracle machine oracle set output p-cylinder parallel computation parallel computation thesis polynomial hierarchy polynomial time hierarchy positive relativization ppui presented probabilistic problem processor proof of Theorem properties prove PSPACE random access machine recursive recursive doubling recursive set reducibility reject result self-reducible sets in NP SIMDAG simulation sparse set steps string subset tally set tape Turing reducibility variables vector machines Volume word of length