2026-07-24T08:26:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10608 2024-03-06T10:46:16Z ddc:004 open_access

Randomness and Intractability in Kolmogorov Complexity Oliveira, Igor Carboni computational complexity randomness circuit lower bounds Kolmogorov complexity We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin’s notion [Leonid A. Levin, 1984] of Kolmogorov complexity. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability. This complexity measure gives rise to a decision problem over strings: MrKtP (The Minimum rKt Problem). We explore ideas from pseudorandomness to prove that MrKtP and its variants cannot be solved in randomized quasi-polynomial time. This exhibits a natural string compression problem that is provably intractable, even for randomized computations. Our techniques also imply that there is no n^{1 - epsilon}-approximate algorithm for MrKtP running in randomized quasi-polynomial time. Complementing this lower bound, we observe connections between rKt, the power of randomness in computing, and circuit complexity. In particular, we present the first hardness magnification theorem for a natural problem that is unconditionally hard against a strong model of computation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Igor Carboni Oliveira 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.32 urn:nbn:de:0030-drops-106087 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.32 eng https://creativecommons.org/licenses/by/3.0/legalcode