Conflict between kolmogorov-complexity tag wiki and usage

Question

Note: we had a similar discussion a while back, but the scope of this question is slightly different and aims to provoke action rather than just being a discussion.

---

Most questions currently tagged with kolmogorov-complexity fall into one of these categories:

1. Challenges about producing a fixed output, whether ascii-art or not. Examples include:
   • We're no strangers to code golf, you know the rules, and so do I
   • 1, 2, Fizz, 4, Buzz
   • "99 Bottles of Beer"
   • Print a 10 by 10 grid of asterisks
   • This is my pillow
   • Build me a brick wall!
   • Lots and lots and lots of alphabet-art challenges
2. Challenges about producing a non-fixed output that matches a certain criterion. Examples:
   • 5 Favorite Letters
   • Words with Blocks
   • Please do my Martian homework
   • Create an Alphabet Song
   • Print some JSON (not tagged with KC, but very similar to the other examples)
3. ascii-art challenges that require input. Examples:
   • Build a triangle without any triangles
   • The IHIH Pyramid
   • Counting Goats to Sleep
   • Print a layered cake
   • Let's draw some Atari ST bombs!
   • Print a cube net of the specified size
   • Mow a Rectangular Lawn
4. Challenges about mapping a finite number of inputs to fixed outputs. Sometimes there are only a few possible inputs, sometimes the input can be broken up into parts. Examples:
   • Code golf for my real friends
   • Translate numbers to French
   • Displaying n with n
   • Turn me 22.5 with a rose
   • Convert Input to Direction
   • Name the Hadrons
   • How fast is my Hot Wheels car? (the KC aspect here is a subset of the challenge)

(Note: challenges mapping infinite (or nearly infinite) inputs to a few fixed outputs are generally tagged classification, or decision-problem if there are only two possible outputs.)

Now, at the top of the kolmogorov-complexity tag wiki, it currently states:

Use this tag for questions about producing a constant output.

And toward the bottom:

kolmogorov-complexity is not about challenges that produce a string that varies depending on a parameter! These challenges, such as Do you want to code a snowman? should usually be tagged with ascii-art or string, or most likely both.

By this definition, challenges in group 1 obviously qualify for the KC tag. Group 2 is slightly fuzzy, but can also be considered within the definition of "producing a constant output"; you're just choosing the output. But groups 3 and 4 are clearly outside the defined scope of the KC tag.

Something here has to change. My question is, what? Should we re-categorize/re-tag challenges in groups 3 and 4, possibly creating a new tag or two for this purpose? Or should the kolmogorov-complexity tag wiki be amended to include groups 3 and/or 4?

Answer 1

Group 4 deserves a tag of its own

Although I tend to personally not enjoy pure kolmogorov-complexity challenges (i.e. group 1), I very much like "reverse kolmogorov complexity" challenges, where you take one of a large number of options as input, and produce corresponding output, but the output is much simpler than the input. (I wrote one of these challenges here, but there are others around.) This is pretty much group 4, as defined here (or possibly a subset of it).

I think this sort of puzzle is not kolmogorov-complexity, but that it deserves its own categorisation (I often use classification, but it doesn't always apply and it's more general). I've seen other people agree with this point of view in comments, too. (Thinking up an appropriate name is hard, though.)

I'm less certain as to what should be done with group 3 (I'm less experienced with those sorts of challenges), so I won't take an opinion on it on this post (except that the eventual choice should not be to tag them the same way as group 4).

Answer 2

The edits which produced the current tag wiki jumped the gun. People with enough rep to see deleted posts can see that there's an answer in the earlier discussion you linked where OP says that he has edited the tag wiki. This answer seems to have been deleted in response to criticism that he should wait for the discussion to be over, so I'm not sure why he didn't roll back the changes at the same time as deleting the answer.

I propose the following rewrite, based on the previous version of the tag wiki:

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.

Note that this only really explicitly addresses your group 1 and part of group 4, but IMO Name the Hadrons makes a much stronger case for belonging to kolmogorov-complexity than your group 2. Really group 4 is too broad. The claims to the tag would be:

• Group 1: Kolmogorov complexity of a simple string
• Group 2: seem to be essentially Kolmogorov complexity meta-questions: find the element of this large set which has the lowest KC
• Group 3: string generation wrapped in a loop?
• Group 4a: Kolmogorov complexity of a dataset
• Group 4b: classification

Answer 3

Give Group 3 its Own Tag

Create a new tag for a challenge that wants a constant output that is affected by the input.

My suggestion is to use kolmogorov as the first word in the new tag, but change the second word for Group 3 challenges (function seems to fit, but it would be very confusing).

Answer 4

We should re-categorize and re-tag group 3 and 4 challenges.

The kolmogorov-complexity tag wiki explicitly states:

Use this tag for questions about producing a constant output.

Google defines constant as:

a situation or state of affairs that does not change.

So we can reword the tag wiki as:

Use this tag for questions about producing output that does not change.

Therefore, I think Kolmogorov complexity challenges should not require input that changes the output. If they require input that changes the output, then that directly violates the reworded tag wiki of Kolmogorov complexity, because the output is "changing", and Kolmogorov complexity should "not change."

Answer 5

Expand to Include Group 3

Many of the more interesting non-string compression kolmogorov-complexity challenges, at least in my opinion, come from an output that varies (slightly or largely) based on an input.