# Perturbative Kolmogorov Complexity Bounds

Are there any known bounds on the impact of changing (for example) one bit in a string on the resulting string's Kolmogorov Complexity? In mathematical terms, does the equation $|K(x) - K(x')|$ (with $K(x)$ as the Kolmogorov Complexity of $x$ and $x'$ as the string resulting from changing an arbitrary bit of $x$) have a non-trivial lower bound?

• There's no reason to expect any lower bound, but there is an upper bound of $O(1)$. May 23 '18 at 21:13
• @YuvalFilmus, not $\lg n$ where $n$ is the length of $x$?
– D.W.
May 23 '18 at 21:59
• Oops... you're right. May 23 '18 at 22:00