<p>Deterministic finite automata transducers (e.g. Moore machines) can be efficiently minimized.</p>

CC BY-SA 4.0
2024-11-11T18:17:24.520Z
In terms of the Chomsky hierarchy, I don't even know if deterministic PDAs are efficiently minimizable (though minimizing them is computable). In terms of circuit classes, minimizing even constant-depth circuits is believed to be hard. I'm not adding this to my answer so as not to discourage other answers, because I'd love to see them. Just describing some limitations to my/our knowledge of such things in a couple directions.
Joshua Grochow
CC BY-SA 4.0
2024-11-12T17:55:21.760Z
Any more than this?  E.g. I think the standard recursive $\gcd(x,y)$ algorithm on integers is in a Kolmogorov-optimal form already, if the operations you are limited to are "just modulo alone".  What about any subset of polynomials?
Daniel Donnelly
CC BY-SA 4.0
2024-11-12T18:45:42.133Z
@IThinkHighlyOfEiligh For GCD check out [Chor-Goldreich](https://doi.org/10.1007/BF01840374). You might also find this related Q interesting: https://cstheory.stackexchange.com/q/608/129.
Joshua Grochow
CC BY-SA 4.0
2024-11-11T16:15:18.010Z
2024-11-11T16:15:18.010Z
Joshua Grochow
<p>I'm interested in applications of optimal programs that convert one formal language into another  (in particular Python to C++) so this seems highly related.  I am thinking along the lines of &quot;how do you generalize / extend&quot; some function.  Say the function simply replaces each letter in the string with another string, then it's by definition a monoid homomorphism and extends easily to any string over the same alphabet, or even extended alphabet and acting on added letters as identity.  But I also thought, what about permutations.  What if the &quot;best&quot; mapping between an input string and an output string is just a permutation of its letters.  I also thought that once I figure out a good theory, these programs are &quot;composable&quot; in the sense that you can substitute a variable for a string in the input language (a new/unused variable), and this gives you a new string to operate on; after which you perform the inverse variable substitution to reach the final result.  Stuff like that is occupying me all of today and previously has occupied my mind for days at a time for a total of about 30 times, but it's taken various algorithms / forms.</p>
<p>So my question is related to the above thoughts.  And it's: do we know of any classes of functions between strings such that the &quot;Kolmogorov-optimal [insert programming language] program&quot; is computable in polynomial time?</p>
<p>For example:  <span class="math-container">$f(x) = x = \text{identity}$</span>.  Clearly it is its own Kolmogorov-optimal function for any space pretty much.  Then take an &quot;atomic constant&quot; function, meaning it only outputs one letter.  Clearly in any reasonable theory we'd define that as optimal of itself as well.  Does there exist some algebraic structure not of the optimal programs themselves, but of programs <em>for which a Kolmogorov-optimal</em> solution can be computed in polynomial time?  Because it's as if you could easily have a subring or ideal of polynomials that are easy enough to do that for, but most-likely it's going to be a multiplicative monoid intuitively speaking.  In other words, its elements are not &quot;optimal&quot;, but they do have an easily computable optimal standard form.</p>
<p>Rules: no probablistic algorithm: it has to be deterministic, which it usually is unless you're approximating an optimal solution, which we are not.</p>

CC BY-SA 4.0
2024-11-12T16:23:22.103Z
I don't understand the close votes. The opening paragraph may be a little rambly, but the question (in the second paragraph) is quite clear. @IThinkHighlyOfEiligh you might highlight the question more by either putting it up top or using ">" to make it indented/quoted. (I don't think that's necessary not-to-close it, just a thought to make it easier for people to jump right to the technical question, whereas the rest is more motivation/examples. Which are good, don't delete! Just some people may want to read the Q first so it helps to make that easy for them.)
Joshua Grochow
<time-complexity><polynomial-time><polynomials><kolmogorov-complexity><kolmogorov>
On what functions on strings of length $n$ are we able to compute the Kolmogorov complexity and also exhibit an optimal program?
Daniel Donnelly
# On what functions on strings of length $n$ are we able to compute the Kolmogorov complexity and also exhibit an optimal program?

(Asked by: username_0 on 2024-11-11)

I'm interested in applications of optimal programs that convert one formal language into another (in particular Python to C++) so this seems highly related. I am thinking along the lines of "how do you generalize / extend" some function. Say the function simply replaces each letter in the string with another string, then it's by definition a monoid homomorphism and extends easily to any string over the same alphabet, or even extended alphabet and acting on added letters as identity. But I also thought, what about permutations. What if the "best" mapping between an input string and an output string is just a permutation of its letters. I also thought that once I figure out a good theory, these programs are "composable" in the sense that you can substitute a variable for a string in the input language (a new/unused variable), and this gives you a new string to operate on; after which you perform the inverse variable substitution to reach the final result. Stuff like that is occupying me all of today and previously has occupied my mind for days at a time for a total of about 30 times, but it's taken various algorithms / forms.

So my question is related to the above thoughts. And it's: do we know of any classes of functions between strings such that the "Kolmogorov-optimal [insert programming language] program" is computable in polynomial time?

For example: $f(x) = x = \text{identity}$. Clearly it is its own Kolmogorov-optimal function for any space pretty much. Then take an "atomic constant" function, meaning it only outputs one letter. Clearly in any reasonable theory we'd define that as optimal of itself as well. Does there exist some algebraic structure not of the optimal programs themselves, but of programs *for which a Kolmogorov-optimal* solution can be computed in polynomial time? Because it's as if you could easily have a subring or ideal of polynomials that are easy enough to do that for, but most-likely it's going to be a multiplicative monoid intuitively speaking. In other words, its elements are not "optimal", but they do have an easily computable optimal standard form.

Rules: no probablistic algorithm: it has to be deterministic, which it usually is unless you're approximating an optimal solution, which we are not.

**Tags:** time-complexity, polynomial-time, polynomials, kolmogorov-complexity, kolmogorov
> **Comments:**
> **username_1**: I don't understand the close votes. The opening paragraph may be a little rambly, but the question (in the second paragraph) is quite clear. @IThinkHighlyOfEiligh you might highlight the question more by either putting it up top or using ">" to make it indented/quoted. (I don't think that's necessary not-to-close it, just a thought to make it easier for people to jump right to the technical question, whereas the rest is more motivation/examples. Which are good, don't delete! Just some people may want to read the Q first so it helps to make that easy for them.)  

---

## 1 answers

### Answer by username_1 on 2024-11-11. Score: 4 | Accepted answer

Deterministic finite automata transducers (e.g. Moore machines) can be efficiently minimized.

> **Comments:**
> **username_1**: In terms of the Chomsky hierarchy, I don't even know if deterministic PDAs are efficiently minimizable (though minimizing them is computable). In terms of circuit classes, minimizing even constant-depth circuits is believed to be hard. I'm not adding this to my answer so as not to discourage other answers, because I'd love to see them. Just describing some limitations to my/our knowledge of such things in a couple directions.  
> **username_0**: Any more than this?  E.g. I think the standard recursive $\gcd(x,y)$ algorithm on integers is in a Kolmogorov-optimal form already, if the operations you are limited to are "just modulo alone".  What about any subset of polynomials?  
> **username_1**: @IThinkHighlyOfEiligh For GCD check out [Chor-Goldreich](https://doi.org/10.1007/BF01840374). You might also find this related Q interesting: https://cstheory.stackexchange.com/q/608/129.  

---

