0
$\begingroup$

The COIN-CHANGING problem is NP-complete, but I am having difficulty finding a proof for its NP-hardness in the form of a reduction from another NP-complete problem to COIN-CHANGING. Apparently, a reduction from SUBSET-SUM to COIN-CHANGING is possible according to this (hopefully old enough) algorithms assignment from Princeton.

Could someone please give a proof of this reducibility?

$\endgroup$

2 Answers 2

1
$\begingroup$

I will use the same notation as the assignment you linked:

$\texttt{SUBSET-SUM}$:

  • Input: $n$ positive integers $w_1, …, w_n$ and an integer target $W$.
  • Question: is there a set $I \subseteq \{1, …, n\}$ such that $\sum\limits_{i\in I}w_i = W$?

$\texttt{COIN-CHANGING}$:

  • Input: $m$ positive integers $1 = c_0 < c_1 < … < c_{m-1}$, an integer target $S$ and a maximum number of coins $T$.
  • Question: is there a multiset $I$ such that $\sum\limits_{i\in I}c_i = S$ and $|I| \leqslant T$?

Following the indications of the assignment, here is my reduction. Given an input of $\texttt{SUBSET-SUM}$, let $b = \max(n+1, W+1)$. Define $c_0 = 1$, and for $i\in\{1, …, n\}$, define: $$c_i = w_i \times b^{n+1} + b^i$$ $$c_i' = b^i$$ Define also: $$S = W\times b^{n+1} + \sum\limits_{i=1}^nb^i$$ Finaly, define $T = n$.

Then $((w_1, …, w_n), W)$ is a positive instance of $\texttt{SUBSET-SUM}$ if and only if $((c_0, …, c_n, c'_1, …, c'_n), S, T)$ is a positive instance of $\texttt{COIN-CHANGING}$.

The idea (detailled proof left to you) is that by selecting at most $n$ coins, no carry can exist in the last $n+1$ digits in base $b$. Since the $i$-th (from right to left, $i\in \{1, …, n\}$) digit of $S$ is $1$, you are allowed to use at most one of each coin. Since the last digit is $0$, you are not allowed to use the coin $c_0$. The coin $c'_i$ is to be picked if the coin $c_i$ is not picked, to insure that the $i$-th digit of the sum is indeed $1$.

This construction is indeed in polynomial time, because each $c_i$, $c_i'$ and $S$ can be written using at most $(n+2)\log_2 b$ bits.

$\endgroup$
0
$\begingroup$

I think that a reduction from exact cover by 3-sets (X3C) is easier: given a set of $X = \{x_1, \dots, x_{3n}\}$ of elements and a collection $S = \{S_1, \dots, S_n\}$ of subsets of $X$ each containing 3 elements, is there a subset $S'$ of $S$ such that each element in $X$ is contained in exactly one set in $S'$?

The reduction is as follows. The amount of change $C$ and each of the coins will be a binary number with $3n + 2\ell$ bits, where $\ell = \lceil \log_2 (1+n) \rceil$. These bits are logically split into a higher part consisting of the $\ell$ most significant bits, a padding part consisting of the next $\ell$ most significant bits, and a lower part consisting of the $3n$ least significant bits. The padding bits will always be set to $0$.

Create one coin $c_i$ for each set $S_i$ by setting the $j$-th least significant bit of the lower part to $1$ if and only if $S_i$ contains $x_j$, and setting the least significant bit of the higher part to $1$ and the other bits to $0$.

Pick $C$ by setting all the $3n$ least significant bits to $1$ and the $\ell$ most significant bits to the binary encoding of $n$.

You can give change using at most $n$ coins if an only if the X3C instance is a yes instance.

Given an exact cover $S'$, you can simply select the $n$ coins corresponding to the sets in $S'$.

Consider now a change-giving strategy that uses at most $n$ cons and notice that it must use exactly $n$ coins since at least $n$ coins are needed to properly set the higher part. Since each of these $n$ coins has exactly $3$ bits set in the lower part, which consists of $3n$ bits, the sets corresponding to the selected coins form an exact cover. To see this imagine adding the values of the selected coins one by one in an arbitrary order. If any two (not necessarily distinct) coins shared the same bit set to $1$ in the lower part, adding the second coin would not set $3$ additional bits to $1$ in the lower part contradicting the fact that $n$ coins were used.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.