# semi-definite programming

## Complexity of square-root sum ★★

Author(s): Goemans

\begin{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.$ \end{question}

Keywords: semi-definite programming