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
Theoretical Comp. Sci. » Complexity

Complexity of square-root sum ★★

Author(s): Goemans

Question   What is the complexity of the following problem?

Given $ a_1,\dots,a_n; k $, determine whether or not $ \sum_i \sqrt{a_i} \leq k. $

Keywords: semi-definite programming

Posted by abie
updated July 1st, 2011
5 comments