http://openproblemgarden.org/op/linear_size_circuits_for_stable_0_1_2_sorting Comments for "Linear-size circuits for stable $0,1 &lt; 2$ sorting?" en http://openproblemgarden.org/op/linear_size_circuits_for_stable_0_1_2_sorting <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/regan_kenneth">Regan</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/theoretical_computer_science">Theoretical Comp. Sci.</a> » <a href="/category/complexity">Complexity</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Can <img class="teximage" src="/files/tex/ee18510ab4140627d7a8df7949d309533b39ebca.png" alt="$ O(n) $" />-size circuits compute the function <img class="teximage" src="/files/tex/43374150a8a220f67049937b9790b7d28eb17fb9.png" alt="$ f $" /> on <img class="teximage" src="/files/tex/f56a45854cf589f1da72c2f64d21b7b4dec2305f.png" alt="$ \{0,1,2\}^* $" /> defined inductively by <img class="teximage" src="/files/tex/f9b67009adb2fef4eb52dc06e1b0a722f93a1168.png" alt="$ f(\lambda) = \lambda $" />, <img class="teximage" src="/files/tex/24d43faf8ea499bed579c16f679f7b353a7c4b2f.png" alt="$ f(0x) = 0f(x) $" />, <img class="teximage" src="/files/tex/b0231ba1329cb9e05670a22b6d96677b863e84cd.png" alt="$ f(1x) = 1f(x) $" />, and <img class="teximage" src="/files/tex/5a41555dd8b0fff8646036b2ec77a62f2e24b2cb.png" alt="$ f(2x) = f(x)2 $" />? </div> </tr></td> </table> </td> </tr> </table> Regan, Kenneth Circuits sorting Theoretical Computer Science Complexity http://openproblemgarden.org/op/linear_size_circuits_for_stable_0_1_2_sorting#comment Thu, 19 Jul 2007 17:57:08 +0200 KWRegan 474 at http://openproblemgarden.org