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?
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.
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 '20 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 '20 at 19:12