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

Importance: Medium ✭✭
Author(s): Regan, Kenneth
Keywords: Circuits
sorting
Recomm. for undergrads: yes
Posted by: KWRegan
on: July 19th, 2007

\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}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

This function moves all 2s in $x$ flush-right, leaving the sequence of 0s and 1s the same, and represents stable topological sort of the partial order $0,1 < 2$. It is linear-time computable in any model that supports the operations of a double-ended queue in $O(1)$ time, including multi-tape Turing machines, but is to me the "easiest" function for which I do not know linear-size circuits. By contrast sorting $0 < 1 < 2$, called the "Dutch National Flag Problem", has $O(n)$-size circuits by counting. It suffices to compute $f(x)$ when $|x|$ is a power of $2$ and exactly half the entries are $2$. For this and more see my \href[Computational Complexity blog item]{http://weblog.fortnow.com/2007/07/concrete-open-problem.html}, PDF file \href[here]{http://www.cse.buffalo.edu/~regan/InfoFlow.pdf}.

Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)


* indicates original appearance(s) of problem.