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(n~(1/2)) bits and some strings require Ω(n~(1/2)) 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。
kolmogorov complexitycomputational complexity
Harry Buhrman、Lance Fortnow、Ilan Newman、Nikolai Vereshchagin
展开 >
CWI, Amsterdam, the Netherlands
STACS 2005; Lecture Notes in Computer Science; 3404
Stuttgart(DE)
Annual Symposium on Theoretical Aspects of Computer Science(STACS 2005); 20050224-26; Stuttgart(DE)
NETL
