We introduce $\mathrm{pKt}$ complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin's $\mathrm{Kt}$ complexity. Using $\mathrm{pKt}$ complexity, we upgrade two recent frameworks that characterize one-way functions ($\mathrm{OWFs}$) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following results:

- $\mathrm{OWFs}$ can be based on the worst-case assumption that $\mathrm{BPEXP}$ is not contained infinitely often in $\mathrm{P}/\mathrm{poly}$ if the failure of symmetry of information for $\mathrm{pKt}$ in the worst-case implies its failure on average.

- (Infinitely-often) $\mathrm{OWFs}$ exist if and only if the average-case easiness of approximating $\mathrm{pKt}$ with two-sided error implies its (mild) average-case easiness with one-sided error.

Previously, in a celebrated result, Liu and Pass (CRYPTO 2021 and CACM 2023) proved that one can base (infinitely-often) $\mathrm{OWFs}$ on the assumption that $\mathrm{EXP} \not\subseteq \mathrm{BPP}$ if and only if there is a reduction from computing $\mathrm{Kt}$ on average with zero error to computing $\mathrm{Kt}$ on average with two-sided error. In contrast, our second result shows that closing the gap between two-sided error and one-sided error average-case algorithms for approximating $\mathrm{pKt}$ is both necessary and sufficient to unconditionally establish the existence of $\mathrm{OWFs}$.