Bjørn Kjos-Hanssen

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 can be reduced to $2+ε$ for any $ε>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$ .

Maximal automatic complexity and context-free languages

Let $A_N$ denote nondeterministic automatic complexity and $L_{k,c}=\{x\in [k]^* : A_N(x)> |x|/c\}.$ In particular, $L_{k,2}$ is the language of all $k$ -ary words for which $A_N$ is maximal, while $L_{k,3}$ gives a rough dividing line between complex and simple. Let $\mathbf{CFL}$ denote the complexity class consisting of all context-free languages. While it is not known that $L_{2,2}$ is infinite, Kjos-Hanssen (2017) showed that $L_{3,2}$ is $\mathbf{CFL}$ -immune but not $\mathbf{coCFL}$ -immune. We complete the picture by showing that $L_{3,2}\not\in\mathbf{coCFL}$ . Turning to Boolean circuit complexity, we show that $L_{2,3}$ is $\mathbf{SAC}^0$ -immune and $\mathbf{SAC}^0$ -coimmune. Here $\mathbf{SAC}^0$ denotes the complexity class consisting of all languages computed by (non-uniform) constant-depth circuits with semi-unbounded fanin. As for arithmetic circuits, we show that $\{x:A_N(x)>1\}\not\in\oplus\mathbf{SAC}^0$ . In particular, $\mathbf{SAC}^0\not\subseteq\oplus \mathbf{SAC}^0$ , which resolves an open implication from the Complexity Zoo.

Strong Medvedev reducibilities and the KL-randomness problem

While it is not known whether each real that is Kolmogorov-Loveland random is Martin-Löf random, i.e., whether $\mathrm{KLR}\subseteq\mathrm{MLR}$ , Kjos-Hanssen and Webb (2021) showed that $\mathrm{MLR}$ is truth-table Medvedev reducible ( $\le_{s,tt}$ ) to $\mathrm{KLR}$ . They did this by studying a natural class Either(MLR) and showing that $\mathrm{MLR}\le_{s,tt}\mathrm{Either(MLR)}\supseteq\mathrm{KLR}$ . We show that Degtev's stronger reducibilities (positive and linear) do not suffice for the reduction of MLR to Either(MLR), and some related results.

The number of languages with maximum state complexity

Câmpeanu and Ho (2004) determined the maximum finite state complexity of finite languages, building on work of Champarnaud and Pin (1989). They stated that it is very difficult to determine the number of maximum-complexity languages. Here we give a formula for this number. We also generalize their work from languages to functions on finite sets.

A conflict between some semantic conditions of Carmo and Jones for contrary-to-duty obligations

We show that Carmo and Jones' condition 5(e) conflicts with the other conditions on their models for contrary-to-duty obligations. We then propose a resolution to the conflict.

A tractable case of the Turing automorphism problem: bi-uniformly $E_0$ -invariant Cantor homeomorphisms

A function $F:2^ω\to 2^ω$ is an $E_0$ -isomorphism if for all $x,y\in 2^ω$ , we have $xE_0y\iff f(x)E_0 f(y)$ , where $xE_0y\iff(\exists a)(\forall n\ge b) x(n)=y(n)$ . If such witnesses $a$ for $xE_0 y$ and for $f(x)E_0 f(y)$ depend on each other but not on $x$ , $y$ , then $F$ is called bi-uniform. It is shown that a homeomorphism of Cantor space which is a bi-uniform $E_0$ -isomorphism can induce only the trivial automorphism of the Turing degrees.

Automatic complexity of shift register sequences

Let $x$ be an $m$ -sequence, a maximal length sequence produced by a linear feedback shift register. We show that $x$ has maximal subword complexity function in the sense of Allouche and Shallit. We show that this implies that the nondeterministic automatic complexity $A_N(x)$ is close to maximal: $n/2-A_N(x)=O(\log^2n)$ , where $n$ is the length of $x$ . In contrast, Hyde has shown $A_N(y)\le n/2+1$ for all sequences $y$ of length $n$ .

From eventually different functions to pandemic numberings

A function is strongly non-recursive (SNR) if it is eventually different from each recursive function. We obtain hierarchy results for the mass problems associated with computing such functions with varying growth bounds. In particular, there is no least and no greatest Muchnik degree among those of the form SNR $_f$ consisting of SNR functions bounded by varying recursive bounds $f$ . We show that the connection between SNR functions and canonically immune sets is, in a sense, as strong as that between DNR (diagonally non-recursive) functions and effectively immune sets. Finally, we introduce pandemic numberings, a set-theoretic dual to immunity.

Kolmogorov structure functions for automatic complexity

For a finite word $w$ we define and study the Kolmogorov structure function $h_w$ for nondeterministic automatic complexity. We prove upper bounds on $h_w$ that appear to be quite sharp, based on numerical evidence.

Nondeterministic automatic complexity of overlap-free and almost square-free words

Shallit and Wang studied deterministic automatic complexity of words. They showed that the automatic Hausdorff dimension $I(\mathbf t)$ of the infinite Thue word satisfies $1/3\le I(\mathbf t)\le 2/3$ . We improve that result by showing that $I(\mathbf t)\ge 1/2$ . For nondeterministic automatic complexity we show $I(\mathbf t)=1/2$ . We prove that such complexity $A_N$ of a word $x$ of length $n$ satisfies $A_N(x)\le b(n):=\lfloor n/2\rfloor + 1$ . This enables us to define the complexity deficiency $D(x)=b(n)-A_N(x)$ . If $x$ is square-free then $D(x)=0$ . If $x$ almost square-free in the sense of Fraenkel and Simpson, or if $x$ is a strongly cube-free binary word such as the infinite Thue word, then $D(x)\le 1$ . On the other hand, there is no constant upper bound on $D$ for strongly cube-free words in a ternary alphabet, nor for cube-free words in a binary alphabet. The decision problem whether $D(x)\ge d$ for given $x$ , $d$ belongs to $NP\cap E$ .

On the complexity of automatic complexity

Generalizing the notion of automatic complexity of individual strings due to Shallit and Wang, we define the automatic complexity $A(E)$ of an equivalence relation $E$ on a finite set $S$ of strings. We prove that the problem of determining whether $A(E)$ equals the number $|E|$ of equivalence classes of $E$ is $\mathsf{NP}$ -complete. The problem of determining whether $A(E) = |E| + k$ for a fixed $k\ge 1$ is complete for the second level of the Boolean hierarchy for $\mathsf{NP}$ , i.e., $\mathsf{BH}_2$ -complete. Let $L$ be the language consisting of all strings of maximal nondeterministic automatic complexity. We characterize the complexity of infinite subsets of $L$ by showing that they can be co-context-free but not context-free, i.e., $L$ is $\mathsf{CFL}$ -immune, but not $\mathsf{coCFL}$ -immune. We show that for each $ε>0$ , $L_ε\not\in\mathsf{coCFL}$ , where $L_ε$ is the set of all strings whose deterministic automatic complexity $A(x)$ satisfies $A(x)\ge |x|^{1/2-ε}$ .

Few paths, fewer words: model selection with automatic structure functions

We consider the problem of finding an optimal statistical model for a given binary string. Following Kolmogorov, we use structure functions. In order to get concrete results, we replace Turing machines by finite automata and Kolmogorov complexity by Shallit and Wang's automatic complexity. The $p$ -value of a model for given data $x$ is the probability that there exists a model with as few states, accepting as few words, fitting uniformly randomly selected data $y$ . Deterministic and nondeterministic automata can give different optimal models. For $x=011\, 110\, 110\, 11$ , the best deterministic model has $p$ -value $0.3$ , whereas the best nondeterministic model has $p$ -value $0.04$ . In the nondeterministic case, counting paths and counting words can give different optimal models. For $x=01100\, 01000$ , the best path-counting model has $p$ -value $0.79$ , whereas the best word-counting model has $p$ -value $0.60$ .

Local initial segments of the Turing degrees

Recent results on initial segments of the Turing degrees are presented, and some conjectures about initial segments that have implications for the existence of non-trivial automorphisms of the Turing degrees are indicated.

Models of the Chisholm set

We give a counter-example showing that Carmo and Jones' condition 5(e) may conflict with other conditions on the models in their paper \emph{A new approach to contrary-to-duty obligations}.

Permutations of the integers induce only the trivial automorphism of the Turing degrees

Let $π$ be an automorphism of the Turing degrees induces by a homeomorphism $φ$ of the Cantor space $2^ω$ such that $φ$ preserves all Bernoulli measures. It is proved that $π$ must be trivial. In particular, a permutation of $ω$ can only induce the trivial automorphism of the Turing degrees.