We say that a distribution &mu is reasonable if there exists a constant s &ge 0 such that &mu( { x | |x| &ge n } ) = &Omega(1/n^s). We prove the following result, which suggests that all DistNP-complete problems have reasonable distributions: If NP contains a DTIME(2ⁿ)-bi-immune set, then every DistNP-complete set has a reasonable distribution. It follows from work of Mayordomo (1994) that the consequent holds if the p-measure of NP is not zero.

Cai and Selman (1996) 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 &mu, the distributional problem (L, &mu) is not polynomial on the &mu-average. We prove the following results, which suggest that distributional hardness is closely related to more traditional notions of hardness.

• If NP contains a distributionally hard set, then NP contains a P-immune set.
• 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.

• If the p-measure of NP is not zero, then there exists a language L that is distributionally hard but not P-bi-immune. \item If the p₂-measure of NP is not zero, then there exists a language L in NP that is distributionally hard but not P-bi-immune.

• Theoretical Computer Science, 234:273-286(2000)