minicomplexity
monotone set programs
 Given a monotone program of operations on a subset of $[h]$, check that running it on a subset that contains $0$ results in a subset that contains $h{-}1$.
 For every $h\geq 1$, monotone set programs$h$ (or just msp$h$) is defined over the alphabet $I_h=[h]{\times}[h]$ of all pairs of numbers from $[h]=\{0,1,\dots,h{-}1\}$. Every string over this alphabet is an instance. Each instance is seen as a program, to be run on a set $\alpha\subseteq[h]$. Every symbol $(j,i)\in[h]{\times}[h]$ is seen as the instruction to add $i$ to $\alpha$ if $j$ is already in $\alpha$: if $\quad j\in\alpha\quad$ then $\quad\alpha\longleftarrow\alpha\cup\{i\}$ . E.g., the program $\mathtt{(1{,}0)(1{,}2)(3{,}2)(3{,}4)}$ over $I_5$ transforms $\alpha$ so that every odd number in it is accompanied by its two even neighbors. (Note that each pair of numbers is an individual symbol.) A program is a positive instance if running it on a set that contains $0$ results in a set that also contains $h{-}1$. Otherwise, the program is a negative instance. E.g., the program $\mathtt{(1{,}0)(1{,}2)(3{,}2)(3{,}4)}$ from above is a negative instance of msp$5$, because e.g. it transforms $\{0,1\}$, which contains $0$, to $\{0,1,2\}$, which does not contain $4$. In contrast, the program $\mathtt{(0{,}1)(1{,}2)(2{,}3)(3{,}4)}$ is a positive instance.
 Introduced by Seiferas 1973, as a simplification of set programs that is still hard enough to be a plausible witness of the difference 1N\2D. Attributed to Charles Rackoff. The name “monotone set programs” is suggested by this site. huh?
 – no record –
 – no record –