# reductions – Reduction of the exact coverage to the total sum in practice!

The reduction of the exact coverage to the sum of subset has already been discussed at this forum. What interests me is the practical aspect of this reduction, which I will discuss in section 2 of this post. For you who do not know these problems, I will define them and show the reduction Exact Cover $$leq_p$$ Sum of subset in section 1. For readers already familiar with these issues, the reduction can move forward. section 2.

## section 1

the Exact coverage defined as follows:

Given a family $${S_j }$$ of subsets of a set $${u_i, i = 1,2, ldots, t }$$ (often called the Universe), find a subfamily $${T_h } subseteq {S_j$$ such as sets $$T_h$$ are disjoint and $$cup T_h = cup S_j = {u_i, i = 1,2, ldots, t }$$.

the Sum of subset is defined as follows:

Given a set of positive integers $$A = {a_1, a_2, ldots, a_r }$$ and another positive integer $$b$$ find a subset $$A subseteq A$$ such as $$sum_ {i in A a_i = b$$.

For the reduction Exact coverage $$leq_p$$ Subset Sum I followed that of Karp R.M. (1972) Reducibility among combinatorial problems

Let $$d = | {S_j } | + 1$$and let
$$epsilon_ {ji} = begin {cases} 1 & text {if} & u_i in S_j, \ 0 & text {if} & u_i notin S_j, end {cases}$$
then
$$a_j = sum_ {i = 1} ^ {t} epsilon_ {ji} d ^ {i-1}, tag {1}$$
and
$$b = frac {d ^ t-1} {d-1}. tag {2}$$

## section 2

In practice (meaning real-world problems), the size of the universe for the exact coverage problem can be very large, for example. $$t = 100$$. This would mean that if you reduce the problem of exact coverage to the problem of the sum of the subsets, the numbers $$a_j$$ content in the set $$A$$ for the sum of subset could be extremely large, and the gap between $$min {A }$$ and $$max {A }$$ can be huge.

For example, let's say $$t = 100$$ and $$d = 10$$, then it is possible to have a $$a_j propto 10 ^ {100}$$ and another $$a_i propto 10$$. Implementing on a computer can be very difficult because adding large numbers with small numbers largely ignores the small number. $$10 ^ {16} + 1 – 10 ^ {16} = 0$$. You can probably see why this could be a problem.

Is it then possible to reduce the exact coverage to the subset sum more conveniently, avoiding large numbers, and having the integers in $$A$$ are of a more reasonable size?

I know that it is possible to multiply both $$A$$ and $$b$$ by an arbitrary factor $$c$$ to resize the problem, but the fact remains this gap between the smallest and the largest integer possible $$A$$ is astronomical.