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$ – Yuval Filmus May 23 '18 at 21:13
  • $\begingroup$ @YuvalFilmus, not $\lg n$ where $n$ is the length of $x$? $\endgroup$ – D.W. May 23 '18 at 21:59
  • $\begingroup$ Oops... you're right. $\endgroup$ – Yuval Filmus May 23 '18 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.