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