minicomplexity
weak landau
 Given a unary string, check that its length is a multiple of some nontrivial summand in a partition of $h$ with maximum least common multiple.
 For every $h\geq 1$, weak landau$h$ (or just wlan$h$) is defined over the unary alphabet $\{\mathtt0\}$. Its instances are all unary strings. To determine positive and negative instances, we use a multiset $[x_1,x_2,\dots,x_k]$ of positive integers which add up to $h$, $x_1,x_2,\dots,x_k\geq 1$   and   $x_1+x_2+\cdots+x_k=h$, and maximize their least common multiple: lcm$(x_1,x_2,\dots,x_k)$ is maximum possible. (This is one of the partitions of $h$ which cause the corresponding value of Landau's function. If more than one exist, we pick one arbitrarily.) Now, an instance is positive if its length $n$ is a multiple of some nontrivial $x_j$: for some $x_j\neq1$ there exists $\lambda$ such that $n=\lambda x_j$. Otherwise, the instance is negative. E.g., the positive instances of wlan$7$ are the unary strings whose length is a multiple of $3$ or $4$ (or both), since the partition of $7$ maximizing the least common multiple is $[x_1,x_2]=[3,4]$.
 Introduced by Chrobak 1986, as an example of a problem in 1N/uny\1D. Implicitly present already in Ott 1964, in an example of a unary 1NFA which can avoid cycles for more than quadratically many steps. The name “weak landau” is suggested by this site. huh? See landau for the variant where $n$ must be a multiple of every $x_j$.
co-1N
co-1N 1D re-1D co-1D rc-1D rc-1N 1D/uny re-1D/uny co-1D/uny co-1N/uny rc-1D/uny rc-1N/uny
 – no record –
 – no record –
 – no record –