Efficiently computable variants of Kolmogorov complexity

Question

Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:

1. It corresponds to an intuition of giving strings with patters or structure a lower complexity than strings without.
2. It allows us to define conditional complexity $K(x|y)$, or even better $K(x|O)$ for some oracle $O$.
3. 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?

Answer 1

Gzip. Cilibrasi and Vitanyi have a really nice article where they use gzip as an approximation of Kolmogorov complexity to do clustering. Clustering by Compression

Answer 2

Basically, almost any machine learning or compression method is an approximation to Kolmogorov complexity:

• If you have any computable probability distribution which assigns your data probability $p(x)$ then, by the Kraft inequality, you have a compressor which compresses your data in $- \log p(x)$ bits.
• If you have any computable compressor C which compresses your data to $n$ bits, then you have $K(x) \leq n + s_C$, where $s_C$ depends on your compressor, but not on $x$ (it's basically the number of bits you need to describe C to your universal Turing machine).

Thus, you can just look for patterns with any compressor or probability distribution and the better they compress your data, the better your upper bound for K(x). Just make sure to add the size of the compressor itself to the size of the compressed data to get the estimate.

Better yet, write a self-contained program that outputs your data. The smaller you can make that program, the smaller $K(x)$ is.

Of course, bounding from above may not be enough. What if your estimate is quite big, what's the probability that $K(x)$ is actually very small? For this you need to make some assumptions, on your data: fix a class of probability distributions (like probabilistic automata), and use a Bayesian mixture over those distributions to compress your data. If your data was actually produced by a probabilistic automaton, the probability that $K$ is substantially smaller than your estimate vanishes exponentially.

You can also use a time bound to define your model class, which leads you to Suresh's answer. Basically, if you assume that your datasource has polynomial time complexity, and you try all polynomial Turing machines to compress it, you can be pretty sure that you've accurately estimated the Kolmogorov complexity. This may still not be that practical, but for lower time bounds, you may be able to compute the full Bayesian mixture, of a good approximation to it.

For technical details see this paper. Disclaimer: I'm one of the authors.

Finally, you should note that $K(x)$ is only meaningful in an asymptotic sense. For any one dataset the value of $K(x)$ can change by a constant from one computer to the next, and that constant can be as large as you like. So take approximations of this kind with a grain of salt.

Answer 3

I thought more about my question, and arrived at possible solution. It has two limitations, it is defined only on strings of length $n = 2^m$ (although I will discuss this more) and it doesn't talk about universal Turing machines, instead following a previous question and using an alternative model of computation.

---

Basically, we can interpret a string $x$ with $|x| = 2^m$ as a function $f_x: \{0,1\}^m \rightarrow \{0,1\}$. Then our complexity measure $K'(x)$ is the size (number of edges) of the unique reduced ordered binary decision diagram (ROBDD; with the standard ordering fixed) representing $f_x$. This satisfies condition [1]. Also, since ROBDDs can be computed in time polynomial in $2^m$, we have an efficient measure.

To satisfy condition [2], we have to modify standard BDDs by allowing an special type on node. Usually nodes are labeled by indexes $i \in \{1,...,m\}$, we will include a special oracle node. For $K(x|y)$ where $|y| = 2^m$ we will allow special nodes in the BDDs as follows:

If we are running a BDD on input $a$ ($|a| = m$) then a normal node labeled by $i$ simply send us down the edge labeled $a_i$. An oracle node will instead send us down an edge labeled $f_y(a)$. Thus, $K'(x|x) = 2$ and with high probability $K'(x|y) \approx K(x)$ for a $y$ picked uniformly at random.

[Note: it is not clear if conditional complexity can still be efficiently computed :(]

Conviniently, we also have sub-additivity since to build an OBDD for $x.y$ we can have a query for the first bit and on $0$ go to the ROBDD for $x$ and on $1$ to the ROBDD for $y$. Thus, we have $K'(x.y) \leq K'(x) + K'(y)$.

---

At the potential cost of sub-additivity we could define $K'(x)$ for any length $x$ by just taking power-of-two chunks and adding their complexities together. For instance for $|x| = 2^m$ and $|y| = 2^l$ with $m > l$ we can define $K'(x.y) = K'(x) + K'(y)$.

There are also some unfortunately limitations with my approach. We can't go much beyond OBDDs, if we consider minimal decision trees or just BDDs then we will snag on the intractability issues addressed in this answer. Even for variable ordering of OBDDs there seems to be intractability results. So it seems OBDDs is the limit of this not-so-similar-to-standard-Kolmogorov-complexity approach.

Answer 4

I'm not an expert, but if you need a practical complexity measure for strings, you can take a look to the Titchener T-complexity measure.

See Titchener's web site for a quick introduction; his papers can be downloaded in pdf format.

Abstract - A new measure of string complexity for finite strings is presented based on a specific recursive hierarchical string production process. From the maximal bound we deduce a relationship between complexity and total information content. ..full article...

I found some papers on practical implementations, too (see for example "A Fast T-decomposition algorithm")

Answer 5

You're looking for resource bounded Kolmogorov complexity. You can start with this paper and branch out.