Problem Instances at given $\alpha>0$.

$(1)$ Given $a_1,\dots,a_{n^\alpha}\in\Bbb Z$ with $|a_i|\in(2^{n-1},2^n-1)$ is there a subset of that sums to $0$?

$(2)$ Given $a_1,\dots,a_{n}\in\Bbb Z$ with $|a_i|\in(2^{n-1},2^n-1)$ is there a subset of size at most $n^\alpha$ that sums to $0$?

At what range of $\alpha$ are these problems $NP$-hard?

Is the problem studied anywhere?

  • 3
    $\begingroup$ For both problems, the empty set yields a trivial solution. $\endgroup$ – Gamow Nov 11 '16 at 9:06
  • 1
    $\begingroup$ Are you sure you want the $a_i$'s to be reals rather than integers? $\endgroup$ – Huck Bennett Nov 16 '16 at 17:39
  • $\begingroup$ @HuckBennett I think for finite precision it would not have mattered. $\endgroup$ – Turbo Nov 22 '16 at 2:46
  • 1
    $\begingroup$ arxiv.org/abs/1311.3054 $\endgroup$ – Kaveh Nov 22 '16 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.