Skip to main content
2 of 2
added 5 characters in body
Zanzi
  • 59
  • 2

Relative Kolmogorov complexity

Given a natural number $n$ denote by $K(n)$ its Kolmogorov complexity.

Let $m, n$ be two natural numbers. The relative Kolmogorov complexity $K_m(n)$ of $n$ with respect to $m$ is the minimum length of a program that takes $m$ as input and outputs $n$.

Question: can the ratio of $K(m)+K_m(n)$ to $K(n)+K_n(m)$ be arbitrarily close to 2?

Zanzi
  • 59
  • 2