Abstract
We present the first characterization of a one-way function by worst-case hardness assumptions: A one-way function exists iff NP is hard in the worst case and "distributional Kolmogorov complexity" is NP-hard under randomized reductions. Here, the t-time bounded distributional Kolmogorov complexity of a string x given a distribution D is defined to be the length of a shortest t-time program that outputs x given as input y drawn from the distribution D with high probability. The characterization suggests that the recent approaches of using meta-complexity to exclude Heuristica and Pessiland from Impagliazzo's five worlds are both sufficient and necessary.