> the existence of a OWF is equivalent to the existence of polynomial-time method for sampling hard *solved* instances for an $\mathrm{NP}$ language (i.e., hard instances together with their witnesses). > [!question] - LP23TCC [On One-Way Functions and Sparse Languages](https://link.springer.com/content/pdf/10.1007/978-3-031-48615-9_8.pdf) > whether the existence of just an average-case hard problem in $\mathrm{NP}$ suffices to get the existence of OWFs: Does the existence of a language in $\mathrm{NP}$ that is hard-on-average imply the existence of OWFs? In Impagliazzo’s language, can we rule out “Pessiland”—a world where $\mathrm{NP}$ is hard on average but OWFs do not exist. - Liu, Y., Pass, R.: On one-way functions and Kolmogorov complexity. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16–19, 2020, pp. 1243–1254. IEEE (2020) > (mild) average-case hardness, w.r.t. the uniform distribution of instances, of a particular natural problem in NP—the time-bounded Kolmogorov Complexity problem—characterizes the existence of OWFs. This problem, however is not average-case complete for $\mathrm{NP}$ so it does not resolve the above question. > Can we identify simple/natural properties of a distribution-language pair $(D, L)$ such that average-case hardness of $L$ with respect to distribution $D$ implies the existence of OWFs?