5
$\begingroup$

The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable language L, the Kolmogorov Complexity of a Decidable Language (KCDL) $^2$ is the size of the smallest program that decides on L.

Is it possible to reduce KC to KCDL? If so, is it possible to do the reverse?

Notes

  1. I don't know if anyone has already defined this concept, so if you have any reference to that definition or even it doesn't make sense, I would be happy if someone commented.
  2. we can generalize this concept to more classes of languages, but I prefer to keep it simple here.

Addendum: $f(w)$ is a computable function that decides $w$ is a word in the language $L$. And, KCDL is define as: $$\text{KCDL}(f) = \min \{ \text{length}(p) : \forall p \in TM, p \text{ compute } f\}$$

And, note that there is a difference between:

  1. the compressed version of a program that computes a function;
  2. the smallest program that computes the same function.

If you want to think of the compressed version of a program as the program itself, you cannot forget to take into account the size of the smallest program that does the decompression. Because, first you need to unzip the program file to be able to use it.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Yes, depending on what kinds of inputs you consider (see below). $KC(x) =^* KCDL(L_x)$, where $L_x$ is the language which consists only of the string $x$, and $=^*$ means equals up to an additive constant.

The reverse is probably not possible (I think I proved this at one point but can't find it right now). The idea is that Kolmogorov complexity can be solved with a Halting Problem oracle, but KCDL (when the input is a TM) is, if I recall correctly, hard for a higher level of the arithmetic hierarchy.

If you want to talk about the complexity of KCDL you also have to be careful to define what the input is. You want the input to be some finite object - languages are generally not. One natural thing for decidable languages is that the input should be a (total) TM. Another possibility is that the input is a TM, along with a proof (in some fixed, formal language) that the TM is total. Other possibilities exist too.

I haven't seen published work about it, but I thought about it a bit in grad school and proved/observed some elementary results. You can do the same for any computable function, not just a language.

Improve this answer
$\endgroup$
13
  • $\begingroup$ For the reverse direction, if $L$ is given as a total Turing machine description $x_L$, then $KC(x_L) =^* KCDL(x_L)$ as well? (if $x_L$ is compressible to $y$ just use $z_L$ that uncompress $y$ and simulate it) $\endgroup$
    – Marzio De Biasi
    Apr 23, 2020 at 9:34
  • 1
    $\begingroup$ There is a definition of kolmogorov complexity of a computable function (see 2.2.3): arxiv.org/abs/cs/0410002 $\endgroup$
    – Raphael Augusto
    Apr 23, 2020 at 12:50
  • $\begingroup$ @MarzioDeBiasi: The issue is that there could be a smaller TM, $s_L$ that also decides the same language $L$, but is smaller than $KC(x_L)$. So you just get $KCDL(x_L) \leq^* KC(x_L)$. $\endgroup$
    – Joshua Grochow
    Apr 23, 2020 at 14:17
  • 1
    $\begingroup$ There is a large study of minimal indices of computable functions. Here's a survey: dl.acm.org/doi/10.1145/2902945.2902957 $\endgroup$
    – Lance Fortnow
    Apr 24, 2020 at 13:56
  • 1
    $\begingroup$ Might depend on the exact encoding of machines, but the definitions are probably not equivalent. Nevertheless, I'd expect many of the results about MIN to carry over to KCDL. $\endgroup$
    – Lance Fortnow
    Apr 26, 2020 at 15:23

Your Answer

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

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