- Definition: The Kolmogorov complexity of a piece of data is the length of the shortest possible description of that data (e.g., the shortest computer program that can generate the data exactly).
- Key Point: There is no algorithmic way to compute the exact Kolmogorov complexity for arbitrary data. Therefore, one cannot systematically achieve “perfect compression” across all possible inputs.