Given a set $𝑁=\{𝑎_1,⋯,𝑎_𝑛\}$ where all $𝑎_𝑖$s are rational positive numbers and $\sum_{i\in N}a_i=1$, find a subset 𝑆⊆𝑁 such that $(\sqrt{2\sum_{i\in S}a_i}-1)^2$ is minimized. Does the appearance of √ make the problem ill-defined with regrading to complexity?
$\begingroup$
$\endgroup$
The appearance of square roots does not make this an ill-defined problem.
Note that $(\sqrt{2\sum_{i\in S}a_i}-1)^2=0$ if $\sum_{i\in S}a_i = 1/2$ and $(\sqrt{2\sum_{i\in S}a_i}-1)^2>0$ otherwise. Therefore, the problem is easily seen to be NP-hard by reduction from subset sum.
answered Feb 26 at 16:52
$\begingroup$
$\endgroup$
In this case, minimizing your expression (given that the sum is positive!) is just to minimize the sum, the square root and square are red herings ($(\sqrt{x} - 1)^2$ is monotone).
-
$\begingroup$ They're not quite red herrings. The expression takes on value $0$ when you pick a subset $S$ such that $\Sigma_{i\in S} i = 1/2$, so you would think that the goal is to make $\Sigma_{i\in S} i$ as close to $1/2$ as possible (I guess this is what you mean). However, the square root messes this up; it gives preference to being an $\epsilon$ under $1/2$ as opposed to being $\epsilon$ above $1/2$. $\endgroup$ – Tom van der Zanden Feb 27 at 17:38
-
$\begingroup$ The function $f(x)=(\sqrt{x}-1)^2$ is not monotone increasing on $[0,\infty]$: it is monotone decreasing on $[0,1]$ and monotone increasing on $[1,\infty]$. $\endgroup$ – D.W.♦ Feb 27 at 19:12
