minicomplexity
list membership
 Given a number and a list of numbers from $[h]$ (in this order), check that the number appears in the list.
 For every $h\geq 1$, list membership$h$ (or just lmem$h$) is defined over the alphabet containing $\mathtt{\#}$ and all numbers of $[h]=\{0,1,\dots,h{-}1\}$. Its instances are all strings where $\mathtt{\#}$ lies between a number on the left and a list of numbers on the right: $i\;\mathtt{\#}\;i_1\;i_2 \cdots i_k$       with $k\geq0$ and $i,i_1,i_2,\dots,i_k\in[h]$. An instance is positive if $i$ equals some $i_j$. Otherwise, $i$ equals no $i_j$ and the instance is negative. E.g., $\mathtt{3\#13041301}$ is a positive instance of lmem$5$, whereas $\mathtt{2\#13041301}$ and $\mathtt{2\#}$ are two negative instances. (Note that strings like $\mathtt{13041}$, $\mathtt{\#13041}$, $\mathtt{12\#13041}$, $\mathtt{12\#41\#130}$ are not instances of the problem.)
 Introduced by Kapoutsis 2011, as a generalization of ordered list membership whose reverse is equivalent to iterated retrocount under $\leq_\text{1D}$. See membership and projection for two additional related problems.
 – no record –
 – no record –
 – no record –