ECCC-Report TR22-074https://eccc.weizmann.ac.il/report/2022/074Comments and Revisions published for TR22-074en-usFri, 20 May 2022 13:27:57 +0300
Paper TR22-074
| On Randomized Reductions to the Random Strings |
Michael Saks,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2022/074We 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.Fri, 20 May 2022 13:27:57 +0300https://eccc.weizmann.ac.il/report/2022/074