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 } | + $ 1and 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.

Thanks in advance!