We develop new characterizations of Impagliazzo's worlds Algorithmica, Heuristica and Pessiland by the intractability of conditional Kolmogorov complexity $\mathrm{K}$ and conditional probabilistic time-bounded Kolmogorov complexity $\mathrm{pK}^t$.

In our first set of results, we show that $\mathrm{NP} \subseteq \mathrm{BPP}$ iff $\mathrm{pK}^t(x \mid y)$ can be computed efficiently in the worst case when $t$ is sublinear in $|x| + |y|$; $\mathrm{DistNP} \subseteq \mathrm{HeurBPP}$ iff $\mathrm{pK}^t(x \mid y)$ can be computed efficiently over all polynomial-time samplable distributions when $t$ is sublinear in $|x| + |y|$; and infinitely-often one-way functions fail to exist iff $\mathrm{pK}^t(x \mid y)$ can be computed efficiently over all polynomial-time samplable distributions for $t$ a sufficiently large polynomial in $|x| + |y|$. These results characterize Impagliazzo's worlds Algorithmica, Heuristica and Pessiland purely in terms of the tractability of conditional $\mathrm{pK}^t$. Notably, the results imply that Pessiland fails to exist iff the average-case intractability of conditional $\mathrm{pK}^t$ is insensitive to the difference between sub-linear and polynomially bounded $t$. As a corollary, while we prove conditional $\mathrm{pK}^t$ to be $\mathrm{NP}$-hard for sublinear $t$, showing $\mathrm{NP}$-hardness for large enough polynomially bounded $t$ would eliminate Pessiland as a possible world of average-case complexity.

In our second set of results, we characterize Impagliazzo's worlds Algorithmica, Heuristica and Pessiland by the distributional tractability of a natural problem, i.e., approximating the conditional Kolmogorov complexity, that is provably intractable in the worst case. We show that $\mathrm{NP} \subseteq \mathrm{BPP}$ iff conditional Kolmogorov complexity can be approximated in the semi-worst case; and $\mathrm{DistNP} \subseteq \mathrm{HeurBPP}$ iff conditional Kolmogorov complexity can be approximated on average over all independent polynomial-time samplable distributions. It follows from a result by Ilango, Ren, and Santhanam (STOC 2022) that infinitely-often one-way functions fail to exist iff conditional Kolmogorov complexity can be approximated on average over all polynomial-time samplable distributions. Together, these results yield the claimed characterizations. Our techniques, combined with previous work, also yield a characterization of auxiliary-input one-way functions and equivalences between different average-case tractability assumptions for conditional Kolmogorov complexity and its variants. Our results suggest that novel average-case tractability assumptions such as tractability in the semi-worst case and over independent polynomial-time samplable distributions might be worthy of further study.