The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Kolmogorov complexity, informally, is the amount of code it takes to describe or produce a constant object, such as a string or image. When posting a challenge in this category, please make sure it adds something new to existing challenges.

From Wikipedia:

In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object.

For example, the string "abababababababababababababababababababab" has a low Kolmogorov complexity because it can be produced with a simple loop:

take 40 $ cycle "ab"

On the other hand, "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd" has a high Kolmogorov complexity, and the shortest way to produce it would (most likely) be to just print it literally:

"4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd"

In the context of code-golf, Kolmogorov complexity is a challenge to compress a specified string or dataset, so a post should be tagged iff the bulk of the challenge is to produce a string or a subset of a dataset which is given in the question.

Examples:

Kolmogorov complexity is undecidable. However, questions effectively crowd-source the approximation of it.

Good challenges add something new to previous challenges.

history | excerpt history