TR04-081 Authors: Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

Publication: 17th September 2004 20:58

Downloads: 2518

Keywords:

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.