# At what parameters is following $NP$-hard?

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?

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