<p>Your reasonable functions are not closed under composition.
Take the reasonable functions <span class="math-container">$f(n):=(n \mod 2) \cdot n$</span> and <span class="math-container">$g(n):=2n$</span>.
Then <span class="math-container">$f \circ g \equiv 0$</span> is not reasonable.</p>
<p>To remedy this domain-splitting issue, one could use an <span class="math-container">$S$</span>-reasonable notion such that <span class="math-container">$\exists_\infty n$</span> is replaced by <span class="math-container">$\forall n \in S \subseteq \mathbb{N}$</span>, and then require <span class="math-container">$f$</span> and <span class="math-container">$g$</span> to be reasonable for the same <span class="math-container">$S$</span>.</p>
<p>As for the application of &quot;standard&quot; functions, I think it holds if the function <span class="math-container">$s$</span> can be computed uniformly and <span class="math-container">$\limsup_{n \to \infty} s(f(n))=\infty$</span> where <span class="math-container">$s$</span> is the standard function.</p>

CC BY-SA 4.0
2024-09-11T10:59:35.127Z
Thanks for the counter example, i guess to make things interesting I should have added that $\alpha$ should be increasing. I'll change the question to reflect that
ULechine
CC BY-SA 4.0
2024-09-10T15:41:31.957Z
2024-09-10T15:41:31.957Z
Nicholas Brandt
<p>Call an increasing function <span class="math-container">$\alpha : \mathbb{N} \rightarrow \mathbb{N}$</span> reasonable if <span class="math-container">$\forall c \in \mathbb{N}, \exists_\infty n, c K^{2n}(n) \leq \alpha (n)$</span>. Where <span class="math-container">$K^t$</span> is the time bounded Kolmogorov complexity and <span class="math-container">$n$</span> is interpreted as its binary representation in the argument of <span class="math-container">$K^{2n}(n)$</span>. As background, any usual function is reasonable, for instance <span class="math-container">$\log^\ast$</span> is reasonable (this is somewhat easily shown).</p>
<p>Questions :
Is reasonability closed under composition (<span class="math-container">$f,g \text{ reasonable} \Rightarrow  f \circ g \text{ reasonable}$</span>)? Closed under application of standard function (e.g. <span class="math-container">$f \text{ reasonable} \Rightarrow  \log(f) \text{ reasonable}$</span>)?</p>
<p><s> I suspect the answer to be no because of the arbitrary constant <span class="math-container">$2$</span> in <span class="math-container">$K^{2n}$</span>, and by taking <span class="math-container">$f=g=K^{1.9n}(n)$</span>. </s></p>
<p><s>If we change the definition to <span class="math-container">$\alpha : \mathbb{N} \rightarrow \mathbb{N}$</span> reasonable iff <span class="math-container">$\exists d\in \mathbb{N}$</span>, <span class="math-container">$\forall c \in \mathbb{N}$</span>, <span class="math-container">$\exists_\infty n$</span>, <span class="math-container">$cK^{dn}(n) \leq \alpha (n)$</span>, is it now closed under composition? </s> <span class="math-container">$\rightarrow$</span> This is shown to be an equivalent question.</p>
<p>Notation : <span class="math-container">$\exists_\infty n, A(n)$</span> means that A(n) is true for infinitely many <span class="math-container">$n$</span>.</p>
<p>Edit : As pointed out by Nicholas Brandt functions must be increasing or <span class="math-container">$f \circ g$</span> may not be reasonable.</p>
<p>Under this definition we may show the following :</p>
<p>Def : Call an increasing function <span class="math-container">$\alpha$</span> d-reasonable if <span class="math-container">$\forall c \in \mathbb{N}, \exists_\infty n, c K^{dn}(n) \leq \alpha (n)$</span>.</p>
<p>Def : Call an increasing function <span class="math-container">$\alpha$</span> ultrareasonable if <span class="math-container">$\forall c \in \mathbb{N}, \exists_\infty n, c K^{1.1 \log(n)}(n) \leq \alpha (n)$</span>.</p>
<p>Theorem : <span class="math-container">$\exists d, \alpha$</span> d-reasonable <span class="math-container">$\Leftrightarrow \alpha$</span> reasonable <span class="math-container">$\Leftrightarrow \alpha $</span> ultrareasonable</p>

CC BY-SA 4.0
2024-08-31T03:06:03.443Z
I'm confused. Do you have a proof that the answer to the first question is "no", or not?
mathworker21
CC BY-SA 4.0
2024-08-31T10:24:51.877Z
$K^{2n}$ should be $K^{cn}$?
Martin Berger
CC BY-SA 4.0
2024-08-31T10:27:11.550Z
What is "Kolmogorov temporal complexity"? You mean time-bounded Kolmogorov complexity?
Martin Berger
CC BY-SA 4.0
2024-08-31T16:05:42.497Z
@mathworker21 no i do not have a proof, actually i now suspect that it holds
ULechine
CC BY-SA 4.0
2024-08-31T16:05:47.010Z
@MartinBerger No i mean $K^{2n}$ in the first definition (or $K^{en}$ if you want but the e should be fixed like e=15 or something). Yes I mean time bounded Kolmogorov complexity
ULechine
CC BY-SA 4.0
2024-09-01T03:43:06.257Z
@ULechine In that case, what's the point of the initial $\forall c  \in \mathbb{N}$ quantification?
Martin Berger
CC BY-SA 4.0
2024-09-01T10:57:41.383Z
@MartinBerger I realized my mistake, I added $c$ at the correct place
ULechine
<complexity><kolmogorov-complexity><kolmogorov>
Is $K^t$ complexity closed under composition
ULechine
# Is $K^t$ complexity closed under composition

(Asked by: username_0 on 2024-08-16)

Call an increasing function $\alpha : \mathbb{N} \rightarrow \mathbb{N}$ reasonable if $\forall c \in \mathbb{N}, \exists\_\infty n, c K^{2n}(n) \leq \alpha (n)$. Where $K^t$ is the time bounded Kolmogorov complexity and $n$ is interpreted as its binary representation in the argument of $K^{2n}(n)$. As background, any usual function is reasonable, for instance $\log^\ast$ is reasonable (this is somewhat easily shown).

Questions :
Is reasonability closed under composition ($f,g \text{ reasonable} \Rightarrow f \circ g \text{ reasonable}$)? Closed under application of standard function (e.g. $f \text{ reasonable} \Rightarrow \log(f) \text{ reasonable}$)?

~~I suspect the answer to be no because of the arbitrary constant $2$ in $K^{2n}$, and by taking $f=g=K^{1.9n}(n)$.~~

~~If we change the definition to $\alpha : \mathbb{N} \rightarrow \mathbb{N}$ reasonable iff $\exists d\in \mathbb{N}$, $\forall c \in \mathbb{N}$, $\exists\_\infty n$, $cK^{dn}(n) \leq \alpha (n)$, is it now closed under composition?~~  $\rightarrow$ This is shown to be an equivalent question.

Notation : $\exists\_\infty n, A(n)$ means that A(n) is true for infinitely many $n$.

Edit : As pointed out by Nicholas Brandt functions must be increasing or $f \circ g$ may not be reasonable.

Under this definition we may show the following :

Def : Call an increasing function $\alpha$ d-reasonable if $\forall c \in \mathbb{N}, \exists\_\infty n, c K^{dn}(n) \leq \alpha (n)$.

Def : Call an increasing function $\alpha$ ultrareasonable if $\forall c \in \mathbb{N}, \exists\_\infty n, c K^{1.1 \log(n)}(n) \leq \alpha (n)$.

Theorem : $\exists d, \alpha$ d-reasonable $\Leftrightarrow \alpha$ reasonable $\Leftrightarrow \alpha $ ultrareasonable

**Tags:** complexity, kolmogorov-complexity, kolmogorov
> **Comments:**
> **username_1**: I'm confused. Do you have a proof that the answer to the first question is "no", or not?  
> **username_2**: $K^{2n}$ should be $K^{cn}$?  
> **username_2**: What is "Kolmogorov temporal complexity"? You mean time-bounded Kolmogorov complexity?  
> **username_0**: @mathworker21 no i do not have a proof, actually i now suspect that it holds  
> **username_0**: @MartinBerger No i mean $K^{2n}$ in the first definition (or $K^{en}$ if you want but the e should be fixed like e=15 or something). Yes I mean time bounded Kolmogorov complexity  
> **username_2**: @ULechine In that case, what's the point of the initial $\forall c  \in \mathbb{N}$ quantification?  
> **username_0**: @MartinBerger I realized my mistake, I added $c$ at the correct place  

---

## 1 answers

### Answer by username_3 on 2024-09-10. Score: 1

Your reasonable functions are not closed under composition.
Take the reasonable functions $f(n):=(n \mod 2) \cdot n$ and $g(n):=2n$.
Then $f \circ g \equiv 0$ is not reasonable.

To remedy this domain-splitting issue, one could use an $S$-reasonable notion such that $\exists\_\infty n$ is replaced by $\forall n \in S \subseteq \mathbb{N}$, and then require $f$ and $g$ to be reasonable for the same $S$.

As for the application of "standard" functions, I think it holds if the function $s$ can be computed uniformly and $\limsup\_{n \to \infty} s(f(n))=\infty$ where $s$ is the standard function.

> **Comments:**
> **username_0**: Thanks for the counter example, i guess to make things interesting I should have added that $\alpha$ should be increasing. I'll change the question to reflect that  

---

