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...

Full description

Bibliographic Details
Main Author: Bjørn Kjos-Hanssen
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
Description
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