Ygtjki

The reduction of Exact Cover to Subset Sum has previously been discussed at this forum. What I'm interested in is the practicality of this reduction, which I will discuss in section 2 of this post. For you who are not familiar with these problems I will define them and show the reduction Exact Cover $leq_p$ Subset Sum in section 1. For the readers who are already familiar with these problems and the reduction can move ahead to section 2.

section 1

The Exact Cover 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_hsubseteqS_j$ such that the sets $T_h$ are disjoint and $cup T_h=cup S_j=u_i, i=1,2,ldots,t$.

The Subset Sum 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 that $sum_iin A'a_i=b$.

For the reduction Exact Cover $leq_p$ Subset Sum I have followed the one given by Karp R.M. (1972) Reducibility among Combinatorial Problems

Let $d=|S_j|+1$, and let
$$
epsilon_ji=begincases1 & textif & u_iin S_j, \ 0 & textif & u_i notin S_j,endcases
$$
then
$$
a_j=sum_i=1^tepsilon_jid^i-1, tag1
$$
and
$$
b = fracd^t-1d-1. tag2
$$

section 2

In practise (meaning for real world problems) the size of the Universe for the Exact Cover problem can be very large, e.g. $t=100$. This would mean that if you would reduce the Exact Cover problem to the Subsets sum problem the numbers $a_j$ contained in the set $A$ for the Subset Sum could be extremely large, and gap between the $minA$ and $maxA$ can therefore be huge.

For example, say $t=100$ and $d=10$, then its possible to have an $a_jpropto 10^100$ and another $a_ipropto 10$. Implementing this on a computer can be very difficult since adding large numbers with small numbers basically ignores the small number, $10^16 + 1 - 10^16 = 0$. You can probably see why this could be a problem.

Is it therefore possible to reduce the Exact Cover to Subset Sum in a more practical way, that avoids the large numbers, and have that 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 rescale the problem, but the fact still remains that gap between possible smallest and largest integer in $A$ is astronomical.

Thanks in advance!

The short answer is no :-)

Why? ... Because SUBSET SUM is weakly NP-complete; you cannot avoid the exponential blowup of the numerical value of the arguments with respect to the input size of the original problem
(in other words the length of the binary representation of the $a_j$ is kept polynomial by the reduction but the values obviously are exponential)

If this was not the case you could use Dynamic Programming to solve an NP-complete problem in polynomial time.