Languages of Words of Low Automatic Complexity Are Hard to Compute

Let $n=|x|$ and suppose $x=x_0\mathrm{\cdots }{x}_{n-1}\in {\mathrm{\Sigma }}^{\ast }$. Now build an NFA as follows: there are $n$ states $\{s_0,\mathrm{\dots },s_{n-1}\}$, with $s_0$ being both the start and unique accepting state. Transitions are given by $s_i\stackrel{x_i}{\to }{s}_{i+1}$ for and $s_{n-1}\stackrel{x_{n-1}}{\to }{s}_0$. It is readily seen that this automaton witnesses , as needed. $◀$ While the previous proposition employs repetition of words to push the non-deterministic automatic complexity down, in the following lemma we show that spacing out bits of information achieves the same effect. W.l.o.g., assume $0\in \mathrm{\Sigma }$. For notation, if $x=x_0\mathrm{\cdots }{x}_{n-1}\in {\mathrm{\Sigma }}^{\ast }$ then define the (Hamming) weight of $x$ by .

Note that, in the statement above, $n$ depends on $q$, which we fixed at the beginning of this section. Before we give the proof, we need the following number-theoretical lemma, called Bertrand’s postulate (for a proof see e.g. [29]). Let $\mathbb{P}$ denote the set of prime numbers.

Fix $c\in \mathbb{N}$. For each $n\in \mathbb{N}\setminus \{0,1\}$, we define a finite sequence of primes by $(p_1(n),\mathrm{\dots },p_c(n))$ as follows: put $p_1(n)=\min \left(\mathbb{P}\cap (\sqrt[c]{n},2\sqrt[c]{n})\right)$ and

Since $n>1$, Bertrand’s Postulate shows that this is well-defined. Now, let

Bertrand’s postulate alongside a short calculation implies , and so

which proves that $Q_i(n)\in O\left(n^{\frac{c-1}{c}}\right)$. This also shows that, in the limit, . Similarly, $Q_i(n)p_i(n)>{(p_1(n))}^c>{(\sqrt[c]{n})}^c=n$ and hence, again in the limit, . For $x\in {\mathrm{\Sigma }}^n$ with $\mathrm{weight}(x)\le c$, write $x=w_0{0}^{{\mathrm{\ell }}_1}{w}_1\mathrm{\cdots }{0}^{{\mathrm{\ell }}_k}{w}_k$ for some $k\le c$. Given our fixed $q\in (0,1/2)$, we now choose $n\in \mathbb{N}$ sufficiently large so that we may assume the following (write $Q_i=Q_i(n)$):

• $\mathrm{■}$

  $|w_i|\le c{Q}_1$ for $i=0,1,\mathrm{\dots },k$.

• $\mathrm{■}$

  ${\mathrm{\ell }}_i\ge Q_1$ for $i=1,\mathrm{\dots },k$.

Now, write ${\mathrm{\ell }}_i=a_i{Q}_i+r_i$ where . Since $Q_i{p}_i>n$ we must have ; otherwise, $|{\mathrm{\ell }}_i|>n=|x|$, a contradiction. Hence, consider the automaton $M$ in Figure 1.

We show that $M$ is as required. First, by definition, $M$ accepts $x$. To show exactness, suppose $y\in {\mathrm{\Sigma }}^n$ and that $M$ accepts $y$. If $x\ne y$, assume w.l.o.g. that $M(y)$ traverses the $0^{Q_1}$-loop fewer than $a_i$-many times. Since $|y|=n$, $M(y)$ must go through the remaining loops more often to make up for the $Q_1$-deficit. However, the equation $Q_1=d_2{Q}_2+\mathrm{\dots }+d_k{Q}_k$ has no integer solution, since $p_1$ divides the right-hand side yet not $Q_1$. Thus, $M$ cannot accept $y$, as needed. Finally, recall that $r_i,|w_i|\le c{Q}_1\in O\left(n^{\frac{c-1}{c}}\right)$. Thus, for $n$ large enough, inspection of the automaton $M$ shows that $A_{Ne}(x)\le 3kc{Q}_1\in O\left(n^{\frac{c-1}{c}}\right)$ for every $x\in {\mathrm{\Sigma }}^n$, and so . $◀$ As a consequence of our proof, we also obtain the following (we thank the anonymous reviewer for pointing this out).

Our next result studies the small-scale structure of words in $L_q$. We say $w$ is a factor of $x$ if there exist $u,v\in {\mathrm{\Sigma }}^{\ast }$ for which $x=uwv$; we write $w⪯x$. If $u\in {\mathrm{\Sigma }}^{+}$ or $v\in {\mathrm{\Sigma }}^{+}$ then $w$ is a proper factor of $x$; we write $w\prec x$. Call a non-empty word $w$ a square if there exists $v\prec w$ for which $w=vv$; we write $w=v^2$.

Note that if $|u|=|v|=|w|$ then the conclusion of Proposition 14 yields a square. To prove the general case of Proposition 14, we again need a classical auxiliary result, in this case due to Lyndon and Schützenberger [27].

Note that the First Lyndon-Schützenberger-Theorem characterises bordered words⁵⁵5For more on bordered words, see e.g. [30]. A more general characterisation is given by the Second Lyndon-Schützenberger-Theorem 18. – those which have a non-trivial decomposition of the form $uw=wv$ – as those generated by powers of a common word $z$. This will be important in the proof of Proposition 14. We also require the following combinatorial lemma.

Consider the list of states $(q_0,\mathrm{\dots },q_n)$. Since , we have . In particular, $n=2qn+(1-2q)n$. Hence, by the pigeonhole principle, there exist at least $(1-2q)n$ indices at which some state is visited a third time. $◀$ We now prove Proposition 14. Call triples $(i,j,k)$ as provided by Lemma 16 loop triples (for $x$). Before we give the proof of Proposition 14, we introduce the following notation: write $x_{[i,j]}=x_i\mathrm{\cdots }{x}_j$. For instance, if $n\ge 4$, then $x_0{x}_1\mathrm{\cdots }{x}_{n-1}=x_{[0,n-1]}=x_{[0,2]}{x}_{[3,n-1]}$.

Let $x\in {\mathrm{\Sigma }}^n$ be as assumed, and suppose $(q_0,\mathrm{\dots },q_n)$ is the run of $M_{Ne}$ which accepts $x$. Observe that if $(i,j,k)$ is a loop triple for $x$ (by Lemma 16 there are at least $(1-2q)n$ many), then the witnessing NFA $M_{Ne}(x)$ has completed at least two loops by the time it has read the word $x_{[0,k-1]}$. There are two cases.

1. 1.

   There exists a loop triple $(i,j,k)$ for which $\max (\left|x_{[i,j-1]}\right|,\left|x_{[j,k-1]}\right|)>(1-2q)\sqrt{n}$.
   Assume w.l.o.g. that $\left|x_{[j,k-1]}\right|\ge \left|x_{[i,j-1]}\right|$ and write $x=x_{[0,i-1]}{x}_{[i,j-1]}{x}_{[j,k-1]}{x}_{[k,n-1]}$. Since $(i,j,k)$ is a loop triple, $q_i=q_j=q_k$, and thus $M_{Ne}(x)$ also accepts the word $x_{[0,i-1]}{x}_{[j,k-1]}{x}_{[i,j-1]}{x}_{[k,n-1]}$. Since $M_{Ne}(x)$ exactly accepts $x$, we have $x_{[j,k-1]}{x}_{[i,j-1]}=x_{[i,j-1]}{x}_{[j,k-1]}$, and so Theorem 15 implies $x_{[i,j-1]}=z^k$ and $x_{[j,k-1]}=z^{\mathrm{\ell }}$ for some $z\in {\mathrm{\Sigma }}^{+}$ and $k,\mathrm{\ell }\in \mathbb{N}$. Since $k,\mathrm{\ell }\ge 1$, the decomposition of $x_{[i,k-1]}$ trivialises into a product of copies of $z$:

   $$x_{[i,k-1]}=x_{[i,j-1]}{x}_{[j,k-1]}=z{z}^{k+\mathrm{\ell }-1}=z^{k+\mathrm{\ell }-1}z$$

   As $\left|z^{k+\mathrm{\ell }-1}\right|\ge \left|x_{[j,k-1]}\right|\ge (1-2q)n>(1-2q)\sqrt{n}$, we are done.

2. 2.

   For all loop triples $(i,j,k)$ we have $\max (\left|x_{[i,j-1]}\right|,\left|x_{[j,k-1]}\right|)\le (1-2q)\sqrt{n}$.
   By Lemma 16, there exist $(1-2q)n$ indices $k$ for which there exist $(i,j)$ such that $(i,j,k)$ is a loop triple. Since every loop in a loop triple has length at most $(1-2q)\sqrt{n}$, the pigeonhole principle gives an $\mathrm{\ell }\le (1-2q)\sqrt{n}$ such that there exist at least $m\ge \sqrt{n}$ such indices $k$ at which a loop of length $\mathrm{\ell }$ was just completed (hence, we only focus on the second loops in each loop triple). Let this set of indices be given in ascending order, denoted by $𝒦=\{k_1,\mathrm{\dots },k_m\}$, with associated loops ${\rho }_1,\mathrm{\dots },{\rho }_m\prec x$, each of length $\mathrm{\ell }$.

   We show that ${\rho }_1$ and ${\rho }_m$ must be disjoint, i.e. share no states along their traversals in $M_{Ne}(x)$. Let $q_{k_1}$ be the origin state of the loop ${\rho }_1$. By definition, ${\rho }_1$ is the second loop in the loop triple $(i_1,j_1,k_1)$. Suppose $\tau$ is the first loop at $q_{k_1}$ so that $\tau {\rho }_1$ is a loop triple at $q_{k_1}$. Then, if we read $b>(1-2q)\sqrt{n}$ letters along the loops at state $q_{k_1}$, then we could concatenate those loops with $\tau$ to obtain a loop triple, one of whose lengths exceeds $(1-2q)\sqrt{n}$, which contradicts the assumption of this case. Therefore, at state $q_{k_1}$, we can only read at most $(1-2q)\sqrt{n}$ letters of the factors contained in ${\rho }_1,\mathrm{\dots },{\rho }_m$, before moving on to a different state, never to return. However, by construction, for every $i\le m$ we know that $x_{k_i}$ appears in ${\rho }_i$, and thus we must read at least $m\ge \sqrt{n}$ letters throughout all loops ${\rho }_1,\mathrm{\dots },{\rho }_m$. Since , we have ; hence, the first and last loops ${\rho }_1$ and ${\rho }_m$ must be disjoint. Thus, $x=u{\rho }_{1}y{\rho }_m{u}^{\prime }$ where $u,y,u^{\prime }\prec x$ and $|{\rho }_1|=|{\rho }_m|=\mathrm{\ell }$. By exact acceptance of $M_{Ne}(x)$, we have

   $$x=u{({\rho }_1)}^{2}y{u}^{\prime }$$

   since $|{\rho }_1|=|{\rho }_m|$. Therefore, ${\rho }_{1}y=y{\rho }_m$, and thus, with $y^{\prime }={\rho }_{1}y$, we have $y^{\prime }{\rho }_m={\rho }_1{y}^{\prime }$. To show that $y^{\prime }$ has the desired length, note that $y{\rho }_m$ must contain the set $\{x_{k_2},\mathrm{\dots },x_{k_m}\}$; the loop ${\rho }_1$, since it is the first loop in $𝒦$, can only contain $x_{k_1}$. Since $n\ge 4$, we have

   $$|y^{\prime }|=|y{\rho }_m|\ge |𝒦|-1=m-1\ge \sqrt{n}-2\ge \frac{\sqrt{n}}{2}.$$

$◀$ We now apply Proposition 14 to go even finer: instead of studying the complexity of $L_q$, we classify the complexity of words in $L_q$, using plain Kolmogorov complexity. Fix an alphabet $\mathrm{\Sigma }$ of cardinality $k$, and let $C_k$ denote the plain Kolmogorov complexity on words in $\mathrm{\Sigma }$:

where $U_k$ is a universal Turing machine on the $k$-element alphabet. For details on Kolmogorov complexity, see e.g. [5].

Its proof – which is included in the full version [4] – requires an extension of Theorem 15, which gives a sufficient and necessary criterion for the decomposition of words with same prefix and suffix. As it will be useful to us in the sequel outside of the proof of Proposition 17, we state it right here in the version of [33].

With $|\mathrm{\Sigma }|=k$ as before, note that the function which maps $x\in {\mathrm{\Sigma }}^{\ast }$ to its $C_k$-witness is an injection. Hence, Proposition 17 immediately yields the following bound on $|L_q|$.

From Corollary 19, we now deduce the Shannon effect for $A_{Ne}$. Originally conjectured by Shannon [36] and proven (and named) by Lupanov for Boolean functions [25, 26], the Shannon effect says that most strings are of almost maximal complexity. We give a definition due to Wegener [45].

By exhibiting upper and lower bounds of complexity for all words, it is readily seen that (plain and prefix-free) Kolmogorov complexity satisfy the Shannon effect [21, 41, 42, 23, 22], as do $A_D$ [35] and $A_n$ [12, 18]. The cardinality argument of Corollary 19 shows:

Fix $q=1/(2+ϵ)$ for some small $ϵ>0$. Since $A_{Ne}(x)\le A_N(x)\le (|x|/2)+1$ (Lemma 6), identifying a suitable lower bound suffices. By Corollary 19, for $o({|\mathrm{\Sigma }|}^n)$-many words $x\in {\mathrm{\Sigma }}^n$ we have $x\in L_q$. Hence, for almost all (as per Definition 20) $x\in {\mathrm{\Sigma }}^n$,

and so $A_{Ne}(x)/|x|$ is sufficiently close to 1/2 for typical large $x$. $◀$