๐ฎ
๐ฎ
The Ethereal
Space-bounded online Kolmogorov complexity is additive
February 04, 2025 ยท The Ethereal ยท ๐ Conference on Computability in Europe
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Bruno Bauwens, Maria Marchenko
arXiv ID
2502.02777
Category
cs.CC: Computational Complexity
Cross-listed
cs.IT
Citations
0
Venue
Conference on Computability in Europe
Last Checked
3 months ago
Abstract
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|$.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Computational Complexity
๐ฎ
๐ฎ
The Ethereal
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
๐ฎ
๐ฎ
The Ethereal
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
๐ฎ
๐ฎ
The Ethereal
The Hardness of Approximation of Euclidean k-means
๐ฎ
๐ฎ
The Ethereal
Slightly Superexponential Parameterized Problems
๐ฎ
๐ฎ
The Ethereal