Skip to main content
1 of 2
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 large?

Zanzi
  • 59
  • 2