Problem Detail: 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{MINtext{-}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 Yes 7. return No I’m not sure about this algorithm though. Can anyone help please?
Asked By : omega
Answered By : Shaull
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 $Ssetminus {s_1}$. It is not hard to verify that this process takes polynomial time.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10690
Related
