Space-bounded online Kolmogorov complexity is additive
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908448515424256 |
|---|---|
| author | Bauwens, Bruno Marchenko, Maria |
| author_facet | Bauwens, Bruno Marchenko, Maria |
| contents | The even online Kolmogorov complexity of a string $x = x_1 x_2 \cdots x_{n}$ is the minimal length of a program that for all $i\le n/2$, on input $x_1x_3 \cdots x_{2i-1}$ outputs $x_{2i}$. The odd complexity is defined similarly. The sum of the odd and even complexities is called the dialogue complexity.
In [Bauwens, 2014] it is proven that for all $n$, there exist $n$-bit $x$ for which the dialogue complexity exceeds the Kolmogorov complexity by $n\log \frac 4 3 + O(\log n)$. Let $\mathrm C^s(x)$ denote the Kolmogorov complexity with space bound~$s$. Here, we prove that the space-bounded dialogue complexity with bound $s + 6n + O(1)$ is at most $\mathrm C^{s}(x) + O(\log (sn))$, where $n=|x|$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02777 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Space-bounded online Kolmogorov complexity is additive Bauwens, Bruno Marchenko, Maria Computational Complexity Information Theory The even online Kolmogorov complexity of a string $x = x_1 x_2 \cdots x_{n}$ is the minimal length of a program that for all $i\le n/2$, on input $x_1x_3 \cdots x_{2i-1}$ outputs $x_{2i}$. The odd complexity is defined similarly. The sum of the odd and even complexities is called the dialogue complexity. In [Bauwens, 2014] it is proven that for all $n$, there exist $n$-bit $x$ for which the dialogue complexity exceeds the Kolmogorov complexity by $n\log \frac 4 3 + O(\log n)$. Let $\mathrm C^s(x)$ denote the Kolmogorov complexity with space bound~$s$. Here, we prove that the space-bounded dialogue complexity with bound $s + 6n + O(1)$ is at most $\mathrm C^{s}(x) + O(\log (sn))$, where $n=|x|$. |
| title | Space-bounded online Kolmogorov complexity is additive |
| topic | Computational Complexity Information Theory |
| url | https://arxiv.org/abs/2502.02777 |