Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:
- It corresponds to an intuition of giving strings with patters or structure a lower complexity than strings without.
- It allows us to define conditional complexity $K(x|y)$, or even better $K(x|O)$ for some oracle $O$.
- It is sub-additive $K(x,y) \leq K(x) + K(y)$.
However it has an awful downside: returning $K(x)$ given $x$ is undecidable.
I have wondered if there is a variant of Kolmogorov complexity $K'(x)$ using a restricted model of computation (either by using weaker languages than TMs, or using resourced bounded TM) that preserves features (1) and (2) (feature (3) is a bonus, but not a must) while being efficiently computable?
The motivation for this question is for use in simulation studies of various toy-models of evolution. Thus an answer that has been used as a 'rough approximation' for Kolmogorov complexity in numeric work before is preferred. However, the goal isn't to go completely experimental, so a relatively simple/clean description language/model-of-computation for $K'$ is preferred, so that it might be possible to prove some reasonable theorems about how drastically $K'$ differs from $K$ and on what kind of strings.
Relates questions
Kolmogorov complexity with weak description languages
Is there a sensible notion of an approximation algorithm for an undecidable problem?