<p>Problem Instances at given $\alpha&gt;0$.</p>

<p>$(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$?</p>

<p>$(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$?</p>

<p>At what range of $\alpha$ are these problems $NP$-hard?</p>

<p>Is the problem studied anywhere?</p>

CC BY-SA 3.0
2016-11-11T09:06:20.487Z
For both problems, the empty set yields a trivial solution.
Gamow
CC BY-SA 3.0
2016-11-16T17:39:23.273Z
Are you sure you want the $a_i$'s to be reals rather than integers?
Huck Bennett
CC BY-SA 3.0
2016-11-22T02:46:52.903Z
@HuckBennett I think for finite precision it would not have mattered.
Turbo
CC BY-SA 3.0
2016-11-22T03:59:55.607Z
https://arxiv.org/abs/1311.3054
Kaveh
<cc.complexity-theory><np-hardness><parameterized-complexity><subset-sum>
At what parameters is following $NP$-hard?
Turbo
# At what parameters is following $NP$-hard?

(Asked by: username_0 on 2016-11-11)

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?

**Tags:** cc.complexity-theory, np-hardness, parameterized-complexity, subset-sum

> **Comments:**
> **username_1**: For both problems, the empty set yields a trivial solution.  
> **username_2**: Are you sure you want the $a_i$'s to be reals rather than integers?  
> **username_0**: @HuckBennett I think for finite precision it would not have mattered.  
> **username_3**: https://arxiv.org/abs/1311.3054  

---

## 0 answers

