Complete distributional problems, hard languages, and resource-bounded measure

AbstractWe say that a distribution μ is reasonable if there exists a constant s⩾0 such that μ({x||x|⩾n})=Ω(1/ns). We prove the following result, which suggests that all DistNP-complete problems have reasonable distributions.If NP contains a DTIME(2n)-bi-immune set, then every DistNP-complete set has a reasonable distribution.It follows from work of Mayordomo [19] that the consequent holds if the p-measure of NP is not zero.Cai and Selman [6] defined a modification and extension of Levin's notion of average polynomial time to arbitrary time-bounds and proved that if L is P-bi-immune, then L is distributionally hard, meaning that, for every polynomial-time computable distribution μ, the distributional problem (L,μ) is not polynomial on the μ-average. We prove the following results, which suggest that distributional hardness is closely related to more traditional notions of hardness. 1.If NP contains a distributionally hard set, then NP contains a P-immune set.2.There exists a language L that is distributionally hard but not P-bi-immune if and only if P contains a set that is immune to all P-printable sets. The following corollaries follow readily 1.If the p-measure of NP is not zero, then there exists a language L that is distributionally hard but not P-bi-immune.2.If the p2-measure of NP is not zero, then there exists a language L in NP that is distributionally hard but not P-bi-immune.