# What is The correct terminology for expressing *this* notion of complexity

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.

• 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. – David Richerby Aug 6 '17 at 15:34
• 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? – Tobi Alafin Aug 6 '17 at 16:35

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