On a subset sum version.

Question

In subset sum we ask 'Given $n$ numbers in $\Bbb Z$, is there a subset of them that sums to $0$?' this is $NP$ complete.

Consider variant:

'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$?'

Is this $NP$ complete? Is there any approximation algorithm?

Answer 1

The problem you describe is equivalent to the EXACT COVER problem, which is known to be NP-complete.

The EXACT COVER problem definition from Wikipedia:

In mathematics, given a collection $S$ of subsets of a set $X$, an exact cover is a subcollection $S^*$ of $S$ such that each element in $X$ is contained in exactly one subset in $S^*$.

EXACT COVER reduces to your problem as follows:

Set $d$ equal to $|X|$. For each element in $X$ map a unique power of $x$ to it, always less than $d$. For each subset of $X$ in $S$ build a polynomial by replacing the set elements with their mappings to powers of $x$ and adding plus signs between them.

Now, any solution to your problem i.e. a set of polynomials that sums to $x^{d-1}+x^{d-2}+\dots+1$ is also a solution to the reduced EXACT COVER problem. The EXACT COVER solution, $S^*$, can be recovered by reversing the set element mappings in the solution polynomials and removing the plus signs.