In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP,P-samp) to (NP,P-comp). To derive these and other related results, a prefix-search algorithm presented by Ben-David et al. will be modified to survive the average polynomial domination.