ECCC-Report TR23-152https://eccc.weizmann.ac.il/report/2023/152Comments and Revisions published for TR23-152en-usSun, 22 Oct 2023 08:09:43 +0300
Paper TR23-152
| One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions |
Yanyi Liu,
Rafael Pass
https://eccc.weizmann.ac.il/report/2023/152Consider 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.Sun, 22 Oct 2023 08:09:43 +0300https://eccc.weizmann.ac.il/report/2023/152