Complexity of square-root sum
Given , determine whether or not
As of a 1998 survey, the complexity of this problem was unknown. I'm not sure if that's still the case. But I wanted to see how easy it was to make a page about it.
This is the key to determining if semi-definite programming is truly solvable in polynomial time (it can be approximated to within using the interior point method or the ellipsoid algorithm in time polynomial in the size of the instance and .
[G] Michal Goemans, Semidefinite Programming and Combinatorial Optimization
* indicates original appearance(s) of problem.