  We show that the complexity of minimal monotone circuits implementing a
monotone version of the permutation operator on $n$ boolean vectors of length
$q$ is $\Theta(qn\log n)$. In particular, we obtain an alternative way to prove
the known complexity bound $\Theta(n\log n)$ for the monotone shift operator on
$n$ boolean inputs.

Computational Complexity