If you express the inputs in unary you get a different running time than if you express them in a higher base (binary, most commonly).
So the question is, for subset sum, what base is appropriate? In computer science we normally default to the following:
- If the input is a list or collection, we express its size as the number of items
- If the input is an integer, we express its size as the number of bits (binary digits)
The intuition here is that we want to take the more "compact" representation.
So for subset sum, we have a list of size $n$ and a target integer of value $t$. Therefore it's common to express the input size as $n$ and $t=2^k$ where $k$ is the number of bits needed to express $t$. So the running time is $O(n 2^k)$ which is exponential in $k$.
But one could also say that $t$ is given in unary. Now the size of $t$ is $t$, and the running time is $O(n t)$, which is polynomial in $n$ and $t$.
In reductions involving subset sum (and other related problems like partition, 3-partition, etc) we must use a non-unary representation if we want to use it as an NP-Hard problem to reduce from.
The Knapsack problem is NP, and any problem in NP can be reduced to an NP complete problem (Cook's Theorem). So to show that the knapsack problem is NP complete it is sufficient to show that an NP-complete problem is reducible to the Knapsack problem. We want to use the exact cover problem to show this. A lot of such reductions can be found in the paper of Karp[1], including the reduction that is described here.
My notation conforms mostly to the notation in this paper.
Assume that $\{S_j,j=1,\ldots,p\}$ is a family of sets that covers the set
$U=\{u_i,i=1,\ldots,t\}$, so
$$\cup_{j=1}^{m} S_j=U$$
We want to check if there is a subfamily $\{S_{j_h},h=1,\ldots,q\}$ of $\{S_j,j=1,\ldots,p\}$ that covers $U$ and where the members of these family are pairwise disjoint. Let $d$ be an arbitrary positive integer. We can assign the number
$$\; \epsilon_{i,j}= \begin{cases}
0,& u_i \not \in S_j \\
1, & u_i \in S_j
\end{cases} \\
a_j=\sum_{j=1}^m \epsilon_{i,j} d^{i-1} \tag{1}$$
to a subset $S_j$.
So $a_j$ is a number that can be written only with digits $0$ and $1$ in a number system with base $d$. It has the digit $1$ on position $i-1$ if and only if $u_i \in S_j$. If $a_{j_1}$ and $a_{j_2}$ are to values assigned to two sets of an exact cover, then there is no position in the representation as an $d$ base number, where both numbers have the digit $1$. The sum $b$ of all the numbers assigned to an exact cover is
$$b=\sum_{i=1}^{t}d^{i-1} \tag{2}$$
if $\{S_j,j=1,\ldots,p\}$ has an exact cover $\{S_{j_h},h=1,\ldots,q\}$ then $x=(x_1,\cdots,x_p)$ with
$$ x_j=
\begin{cases}
1 & \text{if}\; j=j_h, \text{for an } h \in \{1,...,q\} \\
0 & \text{if}\; j\ne j_h, \text{for all } h \in \{1,...,q\} \\
\end{cases}$$
is one solution of the
of the 0-1-Knaspack problem
$$\sum_{i=1}^{p} a_i x_i=b$$
where $a_j$ and $b$ are defined in $(1)$ and $(2)$.
If we select the base $d=p+1$ (or larger) fo all the $2^p$ 0-1-sums no carry will occurr when adding them. So when ome of them sum up to be, there summands con't have 1s on the same place.
[1] Richard M. Karp: Reducibility Among Combinatorial Problems
In: R. E. Miller and J. W. Thatcher (Hrsg.): Complexity of Computer Computations.
Plenum Press, New York, 1972,
p. 85–103
Best Answer
Here's the reduction I thought of first; there may be others equally simple.
We suppose we have a magic machine $M$ which can solve instances of subset-sum, but only when the target sum is even. We want to use this to solve all instances of subset-sum. Suppose the given instance has a set of numbers $N$ and asks us to find a subset $S\subset N$ whose sum is $n$. If $n$ is even we can hand the problem to the machine and use the solution directly; the only interesting case is what to do when $n$ is odd. Then let $o$ be some odd number larger than $\sum N$. We can take $o=1+\sum N$ if that is odd, and otherwise $o = 2+\sum N$. Clearly we can calculate $o$ in polynomial time.
Then hand the machine $N\cup\{o\}$ and ask it to find a subset that adds up to the target sum $o+n$, which it will do, because $o+n$ is even. It will give us back a set $S\subset N\cup\{o\}$ such that $\sum S = o+n$.
We can be sure that $o\in S$ because otherwise $S\subset N$ and so $\sum S\le \sum N \lt o \lt o+n$ which we know is not the case. Then $S\setminus\{o\}$ is the subset we want because it is a subset of $N$, and $\sum(S\setminus\{o\}) = \sum S - o = n+o-o = n$.