ProceedingsComputer Society Press of the IEEE, 1991 - Computational complexity |
From inside the book
Results 1-3 of 53
Page 73
... poly This cannot be improved to placing sets in P since there exists arbitrarily hard sets A such that ( m ) [ FA Є FQ ( 1 , A ) ] [ 2 ] . structive finite information is coded into the Turing machine ; in many proofs that sets are in P / ...
... poly This cannot be improved to placing sets in P since there exists arbitrarily hard sets A such that ( m ) [ FA Є FQ ( 1 , A ) ] [ 2 ] . structive finite information is coded into the Turing machine ; in many proofs that sets are in P / ...
Page 97
... P / poly and the class of sets with polynomial size circuits , one can easily fix some set Eo so that for each L , a function g satisfying the above with Eo is regarded as a circuit generator , that is , g ( 0 ′′ ) denotes the circuit ...
... P / poly and the class of sets with polynomial size circuits , one can easily fix some set Eo so that for each L , a function g satisfying the above with Eo is regarded as a circuit generator , that is , g ( 0 ′′ ) denotes the circuit ...
Page 98
Theorem 4.3 . There is a set in P / poly that is not in PF - SELF gen . = Proof . Note that P / poly RT ( SPARSE ) and that PF - SELFgen CP - SELF . Thus , the set A de- fined at Theorem 3.1 clearly satisfies the theorem . ᄆ We note ...
Theorem 4.3 . There is a set in P / poly that is not in PF - SELF gen . = Proof . Note that P / poly RT ( SPARSE ) and that PF - SELFgen CP - SELF . Thus , the set A de- fined at Theorem 3.1 clearly satisfies the theorem . ᄆ We note ...
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