3
$\begingroup$

Partition problem is well known ( http://en.wikipedia.org/wiki/Partition_problem ).

Let's add an additional condition: sizes of both sets should be equal. Is there a pseudo-polynomial solution to that problem?

1 Answers 1

2

Yes. Given a list $S$ of positive integers, add $\max(S)\cdot \mathrm{length}(S)$ to each element, and denote the resulting list by $S'$. Run the algorithm for the partition problem on $S'$, and accept if and only if it accepts. This is correct because partitions $S'=S'_1\cup S'_2$ are equivalent to partitions $S=S_1\cup S_2$ where $|S_1|=|S_2|$.

  • 0
    Yep. Another reduction would be to send $s\in S$ to $1+s\cdot \mathrm{length}(S)$.2012-10-19