ProceedingsComputer Society Press of the IEEE, 1991 - Computational complexity |
Contents
Counting Classes Are at Least as Hard as the PolynomialTime Hierarchy | 2 |
PP Is Closed under TruthTable Reductions | 12 |
GapDefinable Counting Classes | 28 |
Copyright | |
31 other sections not shown
Other editions - View all
Common terms and phrases
algorithm approximation AuxPDA Beigel binary bits Boolean function cell circuits closure properties co-NP complexity classes Complexity Theory Computer Science construction Corollary counting classes decision problem define Definition denote depth deterministic disjunction encoding equivalent exists EXPTIME fan-in first-order formula function f gap-definable gates graph hard hierarchy IEEE implies input integer interactive proof systems Kolmogorov complexity language Lemma length logic logspace lower bound m₁ monoid NC¹ node nondeterministic NP-complete number of accepting obtain optimization problems oracle oracle Turing machine output P/poly PH collapses polynomial hierarchy polynomial-time predicate prob probabilistic probability Proc processor Proof of Theorem Proposition protocol prove PSPACE quantifier queries random recursive reducible relativized restriction self-reducible Semi-Unbounded sequence SIAM simulation space sparse set strategy string subexponential subset threshold tion truth-table truth-table reducible Turing machine USAT variables Wigderson