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 $\omega(\log(n))$-approximating the Kolmogorov complexity is in AM $\cap$ coAM. On the other hand, using results of Hirahara [H20], 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', there is a polynomial t such that if there is a randomized time t' non-adaptive reduction (satisfying a natural honesty condition) from SAT to $\omega(\log(n))$-approximating $K^t$ complexity, then either NE = coNE or E has sub-exponential size non-deterministic circuits infinitely often.