0
$\begingroup$

Could the following "Surd Partition" problem be NP complete? Note that if the square roots are omitted in the following then the problem is well known to have a polynomial solution.

Surd Partition

Instance: A collection of positive integers $b_{i}, i=1,..,n$ such that $1 \leq b_{1}\leq b_{2}\leq..\leq b_{n}\leq n$

Question: Is there a subset S of {1,2,..,n} in which

\begin{eqnarray} \left| \sum_{i\in S} \sqrt{b_{i}} - \sum_{i\in S^c} \sqrt{b_{i}} \right| < 1? \end{eqnarray}

$\endgroup$
5
  • 2
    $\begingroup$ What is the polynomial solution for the result of removing square roots from that problem? $\;$ $\endgroup$
    – user5810
    Jan 16, 2015 at 2:41
  • $\begingroup$ @RickyDemer: en.wikipedia.org/wiki/… . $\endgroup$ Jan 16, 2015 at 12:16
  • $\begingroup$ As far as I can see, the problem as stated is not even known to be in NP: if you fix $S$, determining whether the sum has absolute value exactly $1$ is a variant of the sum of square roots problem, which is only known to be in the counting hierarchy. I don't see how having the $b_i$ in unary would necessarily help, as the sum has still length $n$. $\endgroup$ Jan 16, 2015 at 12:45
  • $\begingroup$ Specifically, per cs.smith.edu/~orourke/TOPP/P33.html , the best known bounds only show that in order to check $\bigl|\sum_S\sqrt{b_i}-\sum_{S^c}\sqrt{b_i}\bigr|<1$ by computing approximations of the square roots, one can get away with $2^{O(n/\log n)}$ bits of accuracy, which is nowhere near polynomial. $\endgroup$ Jan 16, 2015 at 14:13
  • $\begingroup$ Thanks so much for the responses. The polynolial solution if the sq roots are removed is given in Garey and Johnsons standard text Computers and Intractability pp90-91. Thanks Emil for your guidance - better to suggest that this problem might be NP-hard. $\endgroup$ Jan 20, 2015 at 0:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.