## Proceedings of the Sixth Annual Structure in Complexity Theory Conference: June 30-July 3, 1991, University of Chicago, Chicago, IllinoisIEEE Computer Society. Technical Committee on Mathematical Foundations of Computing, University of Chicago |

### What people are saying - Write a review

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

### Contents

PP Is Closed under TruthTable Reductions | 12 |

GapDefinable Counting Gasses | 28 |

A Survey | 62 |

Copyright | |

18 other sections not shown

### Other editions - View all

### Common terms and phrases

accepting paths algorithm Beigel binary bits Boolean functions circuits class of sets closure properties co-NP complexity classes Complexity Theory Computer Science construction Corollary counting classes define Definition denote depth deterministic encoding equivalent exists EXPTIME finite formula Fortnow func G SAT GapP gates graph hard Hemachandra hierarchy IEEE implies input integer interactive proof interactive proof systems ISBN Kolmogorov complexity language Lemma length lower bound monoid nodes nondeterministic NP-complete number of accepting obtain Ogiwara one-way functions optimization problems oracle oracle Turing machine output P/poly PH collapses plexity polynomial hierarchy polynomial-time predicate prob probabilistic probability Proc processor Proof of Theorem proof systems Proposition protocol prove PSPACE quantifier queries random recursive reducible relativized satisfies self-reducible sequence simulation space sparse set string subexponential subset threshold tion truth-table reducible truth-table reductions Turing degree Turing machine Turing transducer variables Wigderson