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 -