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 kolmogorov-complexity iff the bulk of the challenge is to produce a string or a subset of a dataset which is given in the question.
Examples:
- We're no strangers to code golf, you know the rules, and so do I asks for a fixed output which has lots of structure, and is the canonical question for strings which are suited to grammar-based compression
- Normal distribution values asks for a fixed output which can be generated mathematically
- Who's that Pokémon? asks for an extract from a dataset, so the bulk of the challenge is to compress an array of strings
Kolmogorov complexity is undecidable. However, kolmogorov-complexity questions effectively crowd-source the approximation of it.
Good kolmogorov-complexity challenges add something new to previous challenges.
