Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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