## Proceedings |

### From inside the book

9 pages matching **polynomial complexity core** in this book

Where's the rest of this book?

Results 1-3 of 9

### What people are saying - Write a review

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

### Contents

On Tally Relativizations of BPComplexity Classes Preliminary Report | 10 |

Decision Trees and Downward Closures Extended Abstract | 29 |

On Uniformity within NC | 47 |

Copyright | |

19 other sections not shown

### Common terms and phrases

1-reversal algorithm alternating Turing machines automaton binary bits Boolean circuit Boolean formula Boolean hierarchy bounding functions circuits class of languages closed under complementation co-NP complete sets complexity classes complexity theory Computer Science configuration conjecture construction context-free languages Corollary defined definition denote deterministic encoding equivalent exists fan-in finite function game automata Godel numberings Hartmanis Hemachandra IEEE implies induction infinite input integer interactive proof systems isomorphism Juris Hartmanis Kolmogorov complexity languages accepted Lemma logspace lower bound nodes nomial nondeterministic notion NP oracle NP-complete oracle machine paper path player plexity poly polynomial complexity core polynomial-time hierarchy probabilistic Proc proper polynomial complexity prove PSPACE quantifiers queries random recursive set relativized Schoning self-reducibility sequence simulate space bounded sparse oracle sparse set strategy strings of length subset symbol tally set tape Theory of Computing tion truth-table reducibility Turing machine