## Proceedings, Volume 11, Part 1996 |

### What people are saying - Write a review

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

### Contents

Parallel Complexity Hierarchies Based on PRAMs | 24 |

Collapsing OracleTape Hierarchies | 33 |

How and Why A Survey | 44 |

Copyright | |

23 other sections not shown

### Common terms and phrases

accepts algorithm approximating automorphism binary Boolean boolean circuit branching programs collapses complexity classes Complexity Theory Computer Science coNPMV constant construction Corollary define definition denote deterministic Dlogtime-uniform edge encoding exists extractors fan-in finite formula free vertex func gate graph graph products hence IEEE implies independent set input bits integer program isomorphism L-printable Lemma logspace lower bound many-one many-one reductions maps min-entropy multivalued functions node nonadaptive nondeterministic Note notion NP-complete NPMV NPSV oracle tape oracle Turing machine output bit p-measure p-selective partial multivalued functions pebble polynomial hierarchy polynomial-time computable Pp-COmp probabilistic problem Proc proof system properties Proposition prove PSPACE queries random bits real number recursive satisfying assignment Selman sequence simulation solution space space-bounded strings of length subgraph subset Symposium test tube Theorem tion truth-table reducible Turing machine uniform variables VC dimension vertex vertices width