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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.