Increasing Kolmogorov Complexity

摘要: How much do we have to change a string increase its Kolmogorov complexity? We show that can the complexity of any non-random length n by flipping $O(\sqrt{n})$ bits and some strings require $\Omega(\sqrt{n})$ bit flips. For given m, also give bounds for increasing m bits.