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?

  • $\begingroup$ I don't understand the approximation part of the question. What would you be approximating? $\endgroup$ – Kyle Jones Feb 23 '16 at 3:29

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.

  • $\begingroup$ I've provided the reduction. $\endgroup$ – Kyle Jones May 11 '16 at 20:42
  • $\begingroup$ like approximately summing in some norm? $\endgroup$ – T.... May 12 '16 at 2:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.