Consider the following problems :
Partition problem : Given a collection of $n$ integers $a_1, a_2, \ldots, a_n$, is there a subset $I~\subset~{1,2, \ldots, n }$ such that $\sum_{i~\in~I}a_i~=~\sum_{i~\not\in~I}a_i$ ?
Subset Sum problem : Given a collection of $n$ integers $a_1, a_2, \ldots, a_n$ and an integer $B$, is there a subset $I~\subseteq~{1,2, \ldots, n }$ such that $\sum_{i~\in~I}a_i~=B$ ?
Give a polynomial time reduction from the partition problem to the subset sum problem.
Give a polynomial time reduction from the subset sum problem to the partition problem.
Posted: Jun 12 '12
Seen: 83 times
Last updated: Jun 12 '12
This is a good exam problem.
JeffE (Jun 13 '12)edit