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:4.     Q.add(S_i)5.     res = solveW(Q, t)6.     if res != none and res = t: return Yes7. return NoI'm not sure about this algorithm though. Can anyone help please?
How to prove polynomial time equivalence?
complexity theory;reductions;p vs np
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.