## Proceedings of the ... Annual Structure in Complexity Theory Conference, Volume 6 |

### What people are saying - Write a review

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

### Contents

PP Is Closed under TruthTable Reductions | 13 |

GapDefinable Counting Classes | 30 |

The Power of Witness Reduction | 43 |

Copyright | |

19 other sections not shown

### Common terms and phrases

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