# How to prove polynomial time equivalence?

Define the problem $W$:

Input: A multi-set of numbers $S$, and a number $t$.

Question: What is the smallest subset $s \subseteq S$ so that $\sum_{k \in s} k = t$, if there is one? (If not, return none.)

I am trying to find some polytime equivalent decision problem $D$ and provide a polytime algorithm for the non-decision problem $W$ assuming the existence of a polytime algorithm for $D$.

Here is my attempt at a related decision problem:

$\mathrm{MIN\text{-}W}$:

Input: A multi-set of numbers $S$, two numbers $t$ and $k$.

Question: Is there a subset $s \subseteq S$ so that $\sum_{k \in s} k = t$ and $|s| \leq k$?

Proof of polytime equivalence:

Assume $W \in \mathsf{P}$.

solveMIN-W(S, t, k):
1. S = sort(S)
2. Q = {}
3. for i=1 to k:
5.     res = solveW(Q, t)
6.     if res != none and res = t: return Yes
7. return No


• Please check the definitions. In particular, you don't show equivalence but only one reduction. Note also that $D \in \mathsf{P}$ is trivial. You might also be interested in this post, and this related discussion. – Raphael Mar 22 '13 at 13:46

The problems you mention here are variations of a problem called SUBSET-SUM, FYI if you want to read some literature on it.

What is $S_i$ in your algorithm? If it's the $i$-th element, then you assume that the minimal set will use the smaller elements, which is not necessarily true - there could be a large element that is equal to $t$, in which case there is a subset of size $1$. So the algorithm doesn't seem correct.

However, as with many optimization problems that correspond to NP-complete problems, you can solve the optimization problem given an oracle to the decision problem.

First, observe that by iterating over $k$ and calling the decision oracle, you can find what is the minimal size $k_0$ of a subset whose sum equals $k$ (but not the actual subset).

After finding the size, you can remove the first element in $S$, and check whether there is still a subset of size $k_0$ - if not, then $s_1$ is surely in a minimal subset, so compute $t-s_1$, and repeat the process with the rest of $S$.

If $s_1$ does not effect the size $k_0$, then repeat the process with $S\setminus \{s_1\}$.

It is not hard to verify that this process takes polynomial time.