1
$\begingroup$

Say for example, I have an algorithm $Al_i$ that produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$, and another algorithm $Al_j$ that also produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$. For the purposes of this question, $Al_j$ and $Al_i$ are the same.
 
Or, if I have two systems that produce the same output given the same input, then we can treat these systems as the same.
 
Generally, if two objects do the same things (produce the same output for identical input, convey the same information as output), then these objects are identical. The processing of the systems are not relevant. We're only concerned with the output of the systems, objects, entities, etc.
 
Now, there are many such identical systems. Say $T_i$ is some set of all identical objects/entities/systems that do some same thing. Let $t_i^*$ be the object in $T_i$ with the smallest Kolmogorov complexity.

Is there a conventional terminology for expressing $t_i^*$?

An example of a $T_i$ may be the set of all proofs for a particular theorem. (Here the Kolmogorov complexity of all theorems includes each intermediate theorem invoked in its proof (so basically each theorem would first be expressed in axioms first and computing the complexity of that expression)). I may be interested in referring to the least complex theorem (using the aforementioned notion of the complexity of the axiomatic expression of the theorem).
 
Things can be defined by form or by function. I understand that Kolmogorov complexity traditionally considers the former, while I am concerned with the Kolmogorov complexity of the latter. A picture has a defined form, and an algorithm that only produces that picture is no different from the picture itself. What about an algorithm that produces different output. We could look at the form of the algorithm, or look at its function. Looking at function, all correct algorithms for a particular problem are identical. Bogosort is identical to quicksort which is identical to mergesort, heapsort, etc.
I am concerned with the smallest Kolmogorov complexity of any sorting algorithm.

Improve this question
$\endgroup$
2
  • $\begingroup$ Isn't this just the minimum Kolmogorov complexity of any program that computes a particular function? Is sorting an example or your actual goal? As Ariel's answer points out, you can always use a custom programming langauge in which the empty string is interpreted as a sorting program. It never makes sense to ask about the "complexity" of a single thing, since the answer is always a constant. Normally, that means there's no "complexity" of operating on some fixed input but, here, it means there's no "complexity" of solving a single problem. $\endgroup$
    – David Richerby
    Commented Aug 6, 2017 at 15:34
  • $\begingroup$ Oh, well it came up in a discussion of proofs, were I was trying to explain what I meant by "shortest proof". Well it's supposed to be in a specific language. I want to refer to the smallest program that does function Y. Is there a shorthand for referring to it? $\endgroup$
    – Tobi Alafin
    Commented Aug 6, 2017 at 16:35

1 Answer 1

Reset to default
1
$\begingroup$

Kolmogorov's complexity is defined relative to a specific representation. It is rather meaningless to ask what is the minimal Kolmogorov complexity of a certain object over all possible representations (obviously, this requires a precise definition for what constitutes a valid representation).

To see why, consider for example the following question: what is the minimal Kolmogorov complexity of the identity function over all admissible numberings? The answer is trivially $1$, since I can encode the identity function as "0" (a single bit string).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Things can be defined by form or by function. I understand that Kolmogorov complexity traditionally considers the former, while I am concerned with the Kolmogorov complexity of the latter. A picture has a defined form, and an algorithm that only produces that picture is no different from the picture itself. What about an algorithm that produces different output. We could look at the form of the algorithm, or look at its function. Looking at function, all correct algorithms for a particular problem are identical. Bogosort is identical to quicksort which is identical to mergesort, heapsort, etc. $\endgroup$
    – Tobi Alafin
    Commented Aug 6, 2017 at 14:38
  • $\begingroup$ I am concerned with the smallest Kolmogorov complexity of any sorting algorithm. $\endgroup$
    – Tobi Alafin
    Commented Aug 6, 2017 at 14:38
  • 1
    $\begingroup$ Without fixing the representation in advance, this becomes trivial (as I mentioned in my answer). In the language where the string "0" encodes a program for mergesort, the Kolmogorov complexity of sorting is 1. If you are asking about the term for "shortest equivalent program", i.e. you fix your representation to be the traditional encoding of Turing machines, then this is classical Kolmogorov complexity (of a computable function). $\endgroup$
    – Ariel
    Commented Aug 6, 2017 at 15:00
  • 1
    $\begingroup$ Actually, Kolmogorov complexity is essentially independent of representation because changing the representation only changes the Kolmogorov complexity up to an additive constant. The problem here is that the question seems to be asking about the "complexity" of a single object and the answer is always going to be "it's a constant"; change the representation and it's just a different constant. Notions of complexity only become interesting when you're talking about classes of objects. $\endgroup$
    – David Richerby
    Commented Aug 6, 2017 at 15:17
  • $\begingroup$ @DavidRicherby The representation issue comes from the minimality request. $\endgroup$
    – Ariel
    Commented Aug 6, 2017 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.