2026-07-23T07:15:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16591 2024-03-06T10:57:52Z ddc:004 open_access

On Randomized Reductions to the Random Strings Saks, Michael Santhanam, Rahul Kolmogorov complexity randomized reductions 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', 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 ω(log(n))-approximating K^t complexity, then either NE = coNE or 𝖤 has sub-exponential size non-deterministic circuits infinitely often. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Saks and Rahul Santhanam 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.29 urn:nbn:de:0030-drops-165912 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.29 eng https://creativecommons.org/licenses/by/4.0/legalcode