On the complexity of automatic complexity

Abstract

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 $\epsilon >0$, $L_{\epsilon }\notin \mathsf{coCFL}$, where $L_{\epsilon }$ is the set of all strings whose deterministic automatic complexity $A(x)$ satisfies $A(x)\ge |x{|}^{1/2-\epsilon }$.