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.
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:
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.
- 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.