# Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?

## After removing multi-sets and sets that have elements that don't exist in $$S$$.

$$S$$ = $$[9,6,7,4,5,1,8]$$

$$C$$ =$$[[9,6,7],[4,5],[1,8]]$$

Transform the values in $$C$$ of the shared index values with $$S$$. (This must be done before touching $$S$$)

$$C$$ = $$[[1,2,3],[4,5],[6,7]]$$

And do the same for $$S$$

$$S$$ = $$[1,2,3,4,5,6,7]$$

Square each $$x$$ integer in both $$S$$ and $$C$$

$$f(x)$$ = $$x^2$$, $$x ∈ S$$ then $$C$$

$$S$$ = $$[1, 4, 9, 16, 25, 36, 49]$$

$$C$$ = $$[[1,4,9],[16,25],[36,49]]$$

Then remove all sets with repeating sums to prevent false positives. This means no $$[1],[1]s...$$ that could be used, to sum up to the total sum of $$S$$, This also means $$[1,4,9]$$ or $$[4,9,1]$$. (leave one though!)

1. After the transformation is complete use subset-sum solver and define total-sum as $$140$$ (total-sum of $$s$$)
2. Define list of integers as a summed up set of $$C$$ = $$[[14],[41],[85]]$$
3. Run Algorithm and get the solution

## Question

Will this reduction of Exact Cover into Subset-Sum every yield a false positive?

If you're not really sure whether a reduction will work, it probably won't. Whenever you are making a reduction you should always have a plan of how to prove it correct.

In this case, we're looking to see whether $$1^2+2^2+3^2+...+n^2$$ can be written as a sum of squares in some other way (which would be a false positive).

We have that $$4^2=2^2+2^2+2^2+2^2$$. This is enough to construct a counterexample.

Let $$S=\{1,2,3,4,5,6,7\}$$ and $$C=\{\{1,2\},\{2,3\},\{2,5\},\{2,6\}\,\{2,7\},\{1,3,4,5,6,7\}\}$$.

There is no exact cover (the only way to get $$4$$ is to take $$\{1,3,4,5,6,7\}$$ but then we cannot take any other set since all of them overlap).

However, we have that:

$$1^2+2^2+3^2+4^2+5^2+6^2+7^2=(1^2+2^2)+(2^2+3^2)+(2^2+5^2)+(2^2+6^2)+(2^2+7^2)$$

Thus, we can conclude the reduction does not work.