An incompressibility theorem for automatic complexity
Forum of Mathematics, Sigma, Tome 9 (2021)
Voir la notice de l'article provenant de la source Cambridge University Press
Shallit and Wang showed that the automatic complexity $A(x)$ satisfies $A(x)\ge n/13$ for almost all $x\in {\{\mathtt {0},\mathtt {1}\}}^n$. They also stated that Holger Petersen had informed them that the constant $13$ can be reduced to $7$. Here we show that it can be reduced to $2+\epsilon $ for any $\epsilon>0$. The result also applies to nondeterministic automatic complexity $A_N(x)$. In that setting the result is tight inasmuch as $A_N(x)\le n/2+1$ for all x.
@article{10_1017_fms_2021_58,
author = {Bj{\o}rn Kjos-Hanssen},
title = {An incompressibility theorem for automatic complexity},
journal = {Forum of Mathematics, Sigma},
publisher = {mathdoc},
volume = {9},
year = {2021},
doi = {10.1017/fms.2021.58},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2021.58/}
}
Bjørn Kjos-Hanssen. An incompressibility theorem for automatic complexity. Forum of Mathematics, Sigma, Tome 9 (2021). doi: 10.1017/fms.2021.58
Cité par Sources :