Dado un método de compresión , y basandonos en la Distancia de Kolmogorov normalizada, asumimos que ese compresor es el mejor posible, por lo tanto, se define la distancia de compresión como:
Donde mientras mejor sea la compresión más se acercará al la distancia de kolmogorov normalizada.