Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-081 | 9th September 2004 00:00

Increasing Kolmogorov Complexity


Authors: Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin
Publication: 17th September 2004 20:58
Downloads: 1345


How much do we have to change a string to increase its Kolmogorov complexity. We show that we can
increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings
Omega(sqrt(n)) bit flips. For a given m, we also give bounds for increasing the complexity of a string by
flipping m bits.
By using constructible expanding graphs we give an efficient algorithm that given any non-random string
of length n will give a small list of strings of the same length, at least one of which will have higher Kolmogorov
complexity. As an application, we show that BPP is contained in P relative to the set of Kolmogorov random
strings. Allender, Buhrman, Koucky, van Melkbeek and Ronneberger building on our techniques later
improved this result to show that all of PSPACE reduces to P with an oracle for the random strings.

ISSN 1433-8092 | Imprint