__
TR23-152 | 14th October 2023 01:46
__

#### One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

**Abstract:**
Consider the recently introduced notion of \emph{probabilistic

time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,

CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.

We show the equivalence of the following:

- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable

distribution $\D$;

- MpK^{poly}P is (mildly) hard-on-average w.r.t. the

\emph{uniform} distribution;

- Existence of one-way functions.

As far as we know, this yields the first natural class of problems where

hardness with respect to any samplable distribution is equivalent

to hardness with respect to the uniform distribution.

Under standard derandomization assumptions, we can show the same result

also w.r.t. the standard notion of time-bounded Kolmogorov

complexity, K^t.