Regan, Kenneth


Linear-size circuits for stable $0,1 < 2$ sorting? ★★

Author(s): Regan

\begin{problem} Can $O(n)$-size circuits compute the function $f$ on $\{0,1,2\}^*$ defined inductively by $f(\lambda) = \lambda$, $f(0x) = 0f(x)$, $f(1x) = 1f(x)$, and $f(2x) = f(x)2$? \end{problem}

Keywords: Circuits; sorting

Syndicate content