An incompressibility theorem for automatic complexity
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 c...
Main Author: | |
---|---|
Format: | Article |
Language: | English |
Published: |
Cambridge University Press
2021-01-01
|
Series: | Forum of Mathematics, Sigma |
Subjects: | |
Online Access: | https://www.cambridge.org/core/product/identifier/S205050942100058X/type/journal_article |
Summary: | 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. |
---|---|
ISSN: | 2050-5094 |