<p>In $\mathsf{NP}$ complete subset sum problem we ask 'Given $n$ numbers in $\Bbb Z$ is there a subset that sums to $0$?'.</p>

<p>Is problem 'Given $n$ of degree at most $d$ polynomials in $\Bbb Z[x]$ with coefficients in $\{0,1\}$ is there a subset of them that sums to $x^{d-1}+x^{d-2}+\dots+1$?' $\mathsf{NP}$ complete?</p>

<p>Is there a nice algorithm if each polynomial has exactly fixed $c\geq2$ terms or is it still $\mathsf{NP}$ complete?</p>

CC BY-SA 3.0
2016-02-20T13:04:21.883Z
If I'm understanding right, you want to select polynomials, such that for every degree $i$, exactly one of your polynomials has coefficient $1$ for the variable of degree $i$.  If so, this appears to be the exact cover problem.  https://en.wikipedia.org/wiki/Exact_cover
SamM
CC BY-SA 3.0
2016-02-20T13:15:26.913Z
@samM could you provide the reduction please?
Turbo
CC BY-SA 3.0
2016-02-20T13:38:32.237Z
@samM Is this association right? $X=\{x^0,x^1,\dots,x^{d-1},x^d\}$ and $\mathcal S$ is set of $n$ polynomials. We look for $\mathcal S^*\subseteq\mathcal S$ such that for each $x^i\in X$ there is an unique $p(x)\in S^*$ for which $x^i$ is a term and there is no other $q(x)\in S^*$ for which $x^i$ is a term.
Turbo
<ds.algorithms><subset-sum>
Is this subset sum NP complete?
Turbo
# Is this subset sum NP complete?

(Asked by: username_0 on 2016-02-20)

In $\mathsf{NP}$ complete subset sum problem we ask 'Given $n$ numbers in $\Bbb Z$ is there a subset that sums to $0$?'.

Is problem 'Given $n$ of degree at most $d$ polynomials in $\Bbb Z[x]$ with coefficients in $\{0,1\}$ is there a subset of them that sums to $x^{d-1}+x^{d-2}+\dots+1$?' $\mathsf{NP}$ complete?

Is there a nice algorithm if each polynomial has exactly fixed $c\geq2$ terms or is it still $\mathsf{NP}$ complete?

**Tags:** ds.algorithms, subset-sum

> **Comments:**
> **username_1**: If I'm understanding right, you want to select polynomials, such that for every degree $i$, exactly one of your polynomials has coefficient $1$ for the variable of degree $i$.  If so, this appears to be the exact cover problem.  https://en.wikipedia.org/wiki/Exact_cover  
> **username_0**: @samM could you provide the reduction please?  
> **username_0**: @samM Is this association right? $X=\{x^0,x^1,\dots,x^{d-1},x^d\}$ and $\mathcal S$ is set of $n$ polynomials. We look for $\mathcal S^*\subseteq\mathcal S$ such that for each $x^i\in X$ there is an unique $p(x)\in S^*$ for which $x^i$ is a term and there is no other $q(x)\in S^*$ for which $x^i$ is a term.  

---

## 0 answers

