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
require
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.