# Conflict between kolmogorov-complexity tag wiki and usage

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 fall into one of these categories:

1. Challenges about producing a fixed output, whether or not. Examples include:
2. Challenges about producing a non-fixed output that matches a certain criterion. Examples:
3. challenges that require input. Examples:
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:

(Note: challenges mapping infinite (or nearly infinite) inputs to a few fixed outputs are generally tagged , or 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:

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 tag wiki be amended to include groups 3 and/or 4?

• Note: on the original discussion, the top answer (+15/-3 at the time of writing) supports changing the definition of the KC tag, while the next answer (+15/-8 at the time of writing) supports sticking to the current definition. – ETHproductions May 15 '17 at 21:20
• More precisely, the top answer supported not changing the definition, and the next answer supported changing it, but it was changed before the top answer was written and not rolled back. – Peter Taylor May 16 '17 at 6:40
• This challenge is the essence of group 3. However, it was not marked KC. – Stephen May 16 '17 at 11:17

# Group 4 deserves a tag of its own

Although I tend to personally not enjoy pure 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 , but that it deserves its own categorisation (I often use , 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).

• I agree that this sort of puzzle deserves its own tag. I don't know where the line should be drawn for "much simpler" though; would you consider this challenge to fall into this category? This one? – ETHproductions May 15 '17 at 23:01
• @ETHproductions: I'd say no, but it wouldn't bother me too much if we decided to include them in whatever tag we came up with. Generally speaking, the exact boundaries of a tag aren't massively important because it exists to ease searching, and you can just disregard results that aren't what you were looking for. – user62131 May 15 '17 at 23:41

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 iff the bulk of the challenge is to produce a string or a subset of a dataset which is given in the question.

Examples:

Kolmogorov complexity is undecidable. However, questions effectively crowd-source the approximation of it.

Good 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 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
• Interesting, I hadn't realized that the current state of the tag wiki was a direct result of the previous discussion. Group 4 does seem to cover too much ground to fit into one tag or set of tags; I'd explain my thoughts on this but it would be too long for a comment, so perhaps I'll put them into an answer. – ETHproductions May 17 '17 at 0:25

# 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).

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

The tag wiki explicitly states:

Use this tag for questions about producing a constant output.

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

• Thanks for your input. Do you have a proposal for how we should re-tag these challenges? – ETHproductions May 15 '17 at 22:32
• @ETHproductions Not yet, but I am thinking about it. – Comrade SparklePony May 15 '17 at 22:32

# Expand to Include Group 3

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