[38] For every set A in P, for all constants , > 0, there is a polynomial p such that for all n and

[38] For every set A in P, for all constants α,  > 0, there is a polynomial p such that for all n and for all but an  fraction of the x ∈ A=n, CDp(x) ≤ min{log d(A=n) + logO(1)(n),(1 + α) log d(A=n) + O(log n)}.

Comments. Source: [H.M. Buhrman, L. Fortnow, and S. Laplante, SIAM J. Comput. 31:3(2001), 887–905].