[Solved]: How to find partition set of a Partition Problem using its decision problem

Problem Detail: 

I understand Partition Problem is NP-complete.

Given we have a magic black box that can answer Yes or No for the partition problem. I was wondering how to come up with a polynomial time algorithm to find the actual set using this black box.

Thank you.

Asked By : formatjam

Answered By : Yuval Filmus

Here is what you would do if instead of PARTITION you had SUBSET-SUM. Given a set $S$ and a target $T$, repeat the following process:

1. Pick some $x \in S$.
2. If $S \setminus \{x\}$ has a subset summing to $T$, remove $x$ from $S$ and go back to 1.
3. Otherwise, remove $x$ from $S$ and replace $T$ with $T - x$. Mark $x$ and go back to 1.

The set of all marked elements at the end of the algorithm is an answer.

This approach doesn't work for PARTITION (why?), but perhaps it helps figuring out how reductions of this sort work. One idea to try for PARTITION is merging elements (replacing $x,y$ with $x+y$). I'll let you work out the details.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24279

3.2K people like this

 Download Related Notes/Documents