  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\not\in\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}$.
