P-Comp Versus P-Samp Questions on Average Polynomial

摘要

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 sample distributions) Is polynomially dominated by P-comp (the class of polynomial - Time computable distributions) then there exists no strong one - Way function.