Complexity of square-root sum

 Importance: Medium ✭✭
 Author(s): Goemans, Michel (?)
 Subject: Theoretical Computer Science » Complexity
 Keywords: semi-definite programming
 Posted by: abie on: July 18th, 2007

\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}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

As of \href[a 1998 survey] {http://www.emis.ams.org/journals/DMJDMV/xvol-icm/17/Goemans.MAN.ps.gz}, 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 $\varepsilon$ using the interior point method or the ellipsoid algorithm in time polynomial in the size of the instance and $\log 1/\varepsilon$.

Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[G] Michal Goemans, \href[Semidefinite Programming and Combinatorial Optimization]{http://www.emis.ams.org/journals/DMJDMV/xvol-icm/17/Goemans.MAN.ps.gz}

* indicates original appearance(s) of problem.

Complexity

The complexity of the problem as stated is worst case O(n^3) in the magnitude of the greatest value a[i]. The reason being that it is a simple sum, as stated, of square roots. The square root operation is O(n^2) in the number of bits, which has a 3.xxx:1 relation to the magnitude of each a[i]. Either the problem is mistated or it has not been significant enough for anyone to waste time on stating the obvious.

Filching 10:00(2)

I think the problem is that you may need to compute square roots to high precision. If you need to know the first m digits in the decimal expansion of sqrt(5), it will probably take time linear in m to find them, even though 5 took only constantly many bits to encode.

A slightly more general

A slightly more general problem (in which the square roots may be subtracted as well as added) is very important in the context of computational geometry, both for actual algorithms and for proving complexity-theoretic bounds on problems, as it encapsulates the difficulty of comparing lengths of polygonal chains; see http://maven.smith.edu/~orourke/TOPP/P33.html.
—David Eppstein

Some update

Quotation from \href[Etessami and Yannakakis, 2007]{http://www.dcs.warwick.ac.uk/~agt2007/SLIDES/KE.pdf}: \begin{itemize} \item [Sqrt-sum problem] is known to be solvable in PSPACE but it has been a major open problem ([GareyGrahamJohnson’76]) whether it is solvable even in NP. \item [Allender et. al.,’06] Showed that Sqrt-Sum reduces to a more general problem, which they showed lies in the 4th level of the Counting Hierarchy ($P^{PP^{PP^{PP}}}$). \end{itemize}

From Allender et al.: square-root sum is in CH

http://ftp.cs.rutgers.edu/pub/allender/slp.pdf

Corollary 1.5 The Sum-of-square-roots problem and the Euclidean Traveling Salesman Problem are in CH.

(CH = Counting hierarchy.)

Do we also know that it is in P^(PP^(PP^PP))?