We introduce \(\textsf{pKt}\) complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin’s \(\textsf{Kt}\) complexity. Using \(\textsf{pKt}\) complexity, we upgrade two recent frameworks that characterize one-way functions ( \(\textsf{OWF}\) ) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following results: Previously, in a celebrated result, Liu and Pass (CRYPTO 2021 and CACM 2023) proved that one can base (infinitely-often) \(\textsf{OWF}\) on the assumption that \(\textsf{EXP} \nsubseteq \textsf{BPP}\) if and only if there is a reduction from computing \(\textsf{Kt}\) on average with zero error to computing \(\textsf{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 \(\textsf{pKt}\) is both necessary and sufficient to unconditionally establish the existence of \(\textsf{OWF}\) .