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 |
| _version_ | 1811156155934703616 |
|---|---|
| author | Bjørn Kjos-Hanssen |
| author_facet | Bjørn Kjos-Hanssen |
| author_sort | Bjørn Kjos-Hanssen |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T04:46:48Z |
| format | Article |
| id | doaj.art-0255db405b4b41148c6061444c212f85 |
| institution | Directory Open Access Journal |
| issn | 2050-5094 |
| language | English |
| last_indexed | 2024-04-10T04:46:48Z |
| publishDate | 2021-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Sigma |
| spelling | doaj.art-0255db405b4b41148c6061444c212f852023-03-09T12:34:52ZengCambridge University PressForum of Mathematics, Sigma2050-50942021-01-01910.1017/fms.2021.58An incompressibility theorem for automatic complexityBjørn Kjos-Hanssen0https://orcid.org/0000-0002-6199-1755Department of Mathematics, University of Hawai‘i at Mānoa, Honolulu, HI 96822, USA; E-mail: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.https://www.cambridge.org/core/product/identifier/S205050942100058X/type/journal_article68Q4568Q30 |
| spellingShingle | Bjørn Kjos-Hanssen An incompressibility theorem for automatic complexity Forum of Mathematics, Sigma 68Q45 68Q30 |
| title | An incompressibility theorem for automatic complexity |
| title_full | An incompressibility theorem for automatic complexity |
| title_fullStr | An incompressibility theorem for automatic complexity |
| title_full_unstemmed | An incompressibility theorem for automatic complexity |
| title_short | An incompressibility theorem for automatic complexity |
| title_sort | incompressibility theorem for automatic complexity |
| topic | 68Q45 68Q30 |
| url | https://www.cambridge.org/core/product/identifier/S205050942100058X/type/journal_article |
| work_keys_str_mv | AT bjørnkjoshanssen anincompressibilitytheoremforautomaticcomplexity AT bjørnkjoshanssen incompressibilitytheoremforautomaticcomplexity |