[Solved]: How to prove polynomial time equivalence?

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{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 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 $S\setminus \{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