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:
- Challenges about producing a fixed output, whether ascii-art or not. Examples include:
- 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)
- ascii-art challenges that require input. Examples:
- 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?