On Randomized Reductions to the Random Strings

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants. As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language L that has a randomized polynomial-time non-adaptive reduction (satisfying a natural honesty condition) to ?(log(n))-approximating the Kolmogorov complexity is in AM ? coAM. On the other hand, using results of Hirahara [Shuichi Hirahara, 2020], it follows that every language in NEXP has a randomized polynomial-time non-adaptive reduction (satisfying the same honesty condition as before) to O(log(n))-approximating the Kolmogorov complexity. As our second main result, we give the first negative evidence against the NP-hardness of polynomial-time bounded Kolmogorov complexity with respect to randomized reductions. We show that for every polynomial t\u27, there is a polynomial t such that if there is a randomized time t\u27 non-adaptive reduction (satisfying a natural honesty condition) from SAT to ?(log(n))-approximating K^t complexity, then either NE = coNE or ? has sub-exponential size non-deterministic circuits infinitely often