We have lot's of challenges that are about producing constant output. For example:

These are very clearly questions, since Kolmogorov-Complexity is

Kolmogorov complexity, informally, is the amount of code it takes to produce a given string of text

However, there are a lot of challenges (generally challenges) that are about producing a given string of text depending on the input. For example:

All of these are not pure KC questions, since the output varies. However, they are all tagged with KC also. Should they be tagged any differently since the output is not constant? Is it worth making a distinction between and ? (Obviously we could come up with a better name if we decide to retag)

  • \$\begingroup\$ This is how I felt about the addition of the Kolmo tag on Number Plate Golf: Parsing \$\endgroup\$ – Beta Decay Aug 22 '16 at 10:07
  • 1
    \$\begingroup\$ I think we have a tag for non-constant-output KC challenges: code-golf :) \$\endgroup\$ – Lynn Aug 25 '16 at 11:03

The tag was initially applied only to what you might term pure Kolmogorov complexity questions: those which asked for a constant output. Its scope has expanded over time, and I have also felt that its application to some questions was overbroadening it. However, to limit it to constant-output questions would be to overnarrow it.


A couple of quotes from Wikipedia (my emphasis):

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output.

The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity

To restrict the tag to constant-output questions (understanding output to mean strings or byte sequences, since writing to stdout is one of our standard output options) is to discard other objects. And to insist on the narrowest possible definition of the term KC is to put pedantry ahead of the value and purpose of the tag system, which is to enable people to find questions of interest to them.

An example

IIRC one of the earliest non-constant-output questions to be tagged (and it turns out that I was the one who tagged it, although I didn't remember that when I went looking for it yesterday) was Who's that Pokémon? It takes one input, an integer, and gives one string as output. There's no mathematical formula[1] which will get the output from the input.

This question could have been written as follows:

Write a function (not a program) which takes no input and returns an array of these 151 elements in this order: ...

Is there any good argument that this rewrite doesn't deserve ? Sure, it's a function rather than a program, but that's only because a program can't output an array but only a string representation of an array.

Or can it? By taking the array index as an input and giving the corresponding element as an output, answers to the question as written are essentially managing to output an array to stdout. So although on a very narrow definition this question might not be KC, there's a strong argument that it's actually asking for the KC of a non-text object even on a fairly narrow definition, and I don't think it's possible reasonably to argue that it doesn't fall within the "broader area encompassing descriptional complexity" mentioned in the second Wikipedia quote.

[1] Ok, you pedants, except a case-wise definition.

  • 6
    \$\begingroup\$ I agree largely with what's here, this makes a strong argument that some of the challenges in question are trivially different from kolmogorov complexity questions. What's not addressed is how questions that would require non finite arrays should be dealt with. As I see it, if there are infinite valid inputs that have different outputs, then answers are no longer just accessing indices in an array. This case seems to be truly different from kolmogorov complexity. \$\endgroup\$ – Liam Aug 24 '16 at 11:15

Kolmogorov complexity is specifically the length of a program (in a given language) that produces the given constant string as output. Note the constant - there is no mention in Kolmogorov complexity theory of non-constant strings (producing one of multiple outputs based on an input parameter). In other words, there is no input.

KC-like challenges which require outputting a string based on an input parameter have nothing to do with Kolmogorov complexity, and should not be tagged as such.

  • \$\begingroup\$ I agree with this. Do you think there should be a tag for KC-like challenges which require outputting a string based on an input parameter? ascii-art is generally pretty good for these, but certainly not always. \$\endgroup\$ – DJMcMayhem Aug 21 '16 at 22:35
  • \$\begingroup\$ @DJMcMayhem Maybe? I have no clue what it should be called, though. \$\endgroup\$ – Mego Aug 21 '16 at 22:36
  • 1
    \$\begingroup\$ Perhaps just string. It's probably the simplest solution. \$\endgroup\$ – DJMcMayhem Aug 21 '16 at 22:41
  • 1
    \$\begingroup\$ I disagree. Each individual output (in, e.g., the IHIH pyramid) is constant, and the input is just a selector to determine which of the constant outputs is selected. Simply because the challenge requires building the selector in addition to the output-maker, which allows for plenty of golfing opportunities, shouldn't mean the challenges aren't KC. \$\endgroup\$ – AdmBorkBork Aug 22 '16 at 19:11
  • 1
    \$\begingroup\$ @TimmyD You can disagree all you like, but that doesn't change the definition of Kolmogorov complexity (the computer science theory). In KC, programs take no input and produce a single constant output. Anything else is not KC. \$\endgroup\$ – Mego Aug 22 '16 at 19:42
  • \$\begingroup\$ @Mego Ah, I thought we were attempting to define it here, rather than re-use definitions from elsewhere. Like how we've defined "programming language" or "truthy/falsey" specifically for the context of this site, which, while inter-related to "standard" definitions, don't quite line up exactly. \$\endgroup\$ – AdmBorkBork Aug 22 '16 at 20:22
  • \$\begingroup\$ @TimmyD That's because "programming language" and "truthy/falsey" are fuzzy definitions outside of this site. Kolmogorov complexity has a very solid definition. \$\endgroup\$ – Mego Aug 22 '16 at 20:26
  • \$\begingroup\$ Makes sense now. I'll retract my downvote if'n I can. \$\endgroup\$ – AdmBorkBork Aug 22 '16 at 20:29
  • 3
    \$\begingroup\$ @PeterTaylor Would you mind fleshing that out a bit and making it a separate answer? :) \$\endgroup\$ – Martin Ender Aug 23 '16 at 14:23

Edit the tag wiki

Personally I feel that Kolmogorov complexity can be extended apply to any string output which has a clear pattern which can be exploited to increase brevity. The tag wiki should be modified to reflect this.

However, Strings with a very high complexity like ("Hello, World!") are certainly not excluded from this tag wiki as DJMcMayhem pointed out. KC should continue to reflect challenges which have a high complexity and may lack tricks to golfing it down. (However most such challenges should be avoided)

This consensus has been shown in multiple questions, and that is why I suggest it. Please vote up/down this proposal however you see fit.

  • \$\begingroup\$ I don't think I really agree with this. You could certainly make a case for keeping/adding the KC tag to ascii art challenges, but this seems to be arguing that KC only fits for strings with a low KC, which does not apply to challenges like "hello world" \$\endgroup\$ – DJMcMayhem Aug 21 '16 at 22:40
  • \$\begingroup\$ @DJMcMayhem whoops, let me readjust my answer to be more inclusive to strings with a high Kolmogorov complexity \$\endgroup\$ – Rohan Jhunjhunwala Aug 21 '16 at 22:41
  • \$\begingroup\$ Does the readjusted proposal make more sense @DJMcMayhem \$\endgroup\$ – Rohan Jhunjhunwala Aug 21 '16 at 22:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .