TY - GEN

T1 - On Randomized Reductions to the Random Strings

AU - Saks, Michael

AU - Santhanam, Rahul

N1 - Funding Information:
Funding Michael Saks: Supported in part by the Simons Foundation under Grant 332622. Rahul Santhanam: Partially funded by EPSRC New Horizons Grant EP/V048201/1.
Funding Information:
This work received support from the Royal Society University Research Fellowship URF\R1\191059 and from the EPSRC New Horizons Grant EP/V048201/1. This research was also partially supported by NSERC Discovery and NSERC CGS M programs.
Publisher Copyright:
© Michael Saks and Rahul Santhanam

PY - 2022/7/1

Y1 - 2022/7/1

N2 - 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 [28], 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′ nonadaptive reduction (satisfying a natural honesty condition) from SAT to ω(log(n))-approximating Kt complexity, then either NE = coNE or E has sub-exponential size non-deterministic circuits infinitely often.

AB - 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 [28], 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′ nonadaptive reduction (satisfying a natural honesty condition) from SAT to ω(log(n))-approximating Kt complexity, then either NE = coNE or E has sub-exponential size non-deterministic circuits infinitely often.

KW - Kolmogorov complexity

KW - randomized reductions

UR - http://www.scopus.com/inward/record.url?scp=85134410652&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134410652&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CCC.2022.29

DO - 10.4230/LIPIcs.CCC.2022.29

M3 - Conference contribution

AN - SCOPUS:85134410652

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 37th Computational Complexity Conference, CCC 2022

A2 - Lovett, Shachar

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 37th Computational Complexity Conference, CCC 2022

Y2 - 20 July 2022 through 23 July 2022

ER -