minicomplexity
landau
 Given a unary string, check that its length is a multiple of every summand in a partition of $h$ with maximum least common multiple.
 For every $h\geq 1$, landau$h$ (or just lan$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 every $x_j$: for every $x_j$ there exists $\lambda$ such that $n=\lambda x_j$. Otherwise, the instance is negative. (Equivalently, the instance is positive if its length is a multiple of the value of Landau's function on $h$.) E.g., the positive instances of lan$7$ are the unary strings whose length is a multiple of $12$, since the partition of $7$ maximizing the least common multiple is $[x_1,x_2]=[3,4]$ (and thus Landau's function on $7$ returns $12$).
 Introduced by Holzer Kutrib 2002, as an example of a problem in co-1N/uny\1N. Implicitly present already in Ott 1964, in an example of a unary 1NFA which starts repeating configurations after more than quadratically many steps. The name “landau” is suggested by this site. huh? See weak landau for the variant where $n$ must be a multiple of some $x_j$.
1N
1N 1D re-1D re-1N co-1D rc-1D 1D/uny 1N/uny re-1D/uny re-1N/uny co-1D/uny rc-1D/uny
 – no record –
 – no record –
 – no record –