ECCC-Report TR19-064https://eccc.weizmann.ac.il/report/2019/064Comments and Revisions published for TR19-064en-usTue, 30 Apr 2019 21:41:08 +0300
Paper TR19-064
| Randomness and Intractability in Kolmogorov Complexity |
Igor Carboni Oliveira
https://eccc.weizmann.ac.il/report/2019/064We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin's notion of Kolmogorov complexity from 1984. 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-eps}-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.Tue, 30 Apr 2019 21:41:08 +0300https://eccc.weizmann.ac.il/report/2019/064