Home » Keyword index

sorting


Theoretical Comp. Sci. » Complexity

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

Author(s): Regan

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 $?

Keywords: Circuits; sorting

Posted by KWRegan
updated July 19th, 2007
add new comment
Syndicate content