# NP hardness of Partition

I'm trying to show that PARTITION is NP-hard. I'm not sure if what I have is correct so I'll write what I have. I tried to reduce it from SUBSET_SUM:

$$PART= \{S\subset\mathbb{Z}|\exists C \subset S: \sum_{x\in C} x=\sum_{x\in S-C}x\}$$ $$SUBSET SUM = \{\langle T,u\rangle| T\subset \mathbb{N}, u \in \mathbb{Z}\quad\exists B\subset T: \sum_{y\in B}y = u\}$$

$$SUBSETSUM \leq_p PART$$

$\text{Let} \quad f\left(\langle T,u\rangle\right)=\langle S\rangle$ be a polytime computable function that accepts an instance of subset sum and outputs an instance of partition.

The basic gist of my proof was that if I made the restriction that my $$u =\sum_{y\in T-B} y$$ and then allowed $T=S$, $B=C$ and $x=y$ I'd prove the equivalence of subset sum and partition.

• Do you have to reduce from subset sum, or are you OK with reduction from any NP-complete problem? – TCSGrad May 7 '14 at 1:51
• I can reduce from any NP complete problem (but I'd like to know if what I've done is correct in any sense), but if possible I'd like to see how different reductions could be done for the same problem. – user119264 May 7 '14 at 1:58
• Try writing your solution in words. It's very hard to follow the way it's presented now. – Yuval Filmus May 7 '14 at 3:56

Your reduction completely ignores $u$. Certainly the answer for SUBSET SUM depends on $u$, doesn't it?
Also, you can't guarantee $x=y$, $B=C$. Rather, given $T$ and $u$, you need to produce $S$ (in polynomial time) such that there is a subset of $T$ summing to $u$ iff $S$ can be partitioned into two equal halves. This is the meaning of reduction.
Your suggestion $S = T$ doesn't work. For example, if $T = \{1,2,3\}$ and $u = 7$ then there is no subset of $T$ summing to $u$ but $S$ can be partitioned as $\{1,2\} \cup \{3\}$.
Here is another suggestion: choose $S = T \cup \{\sum T - 2u\}$. The idea here is that if $A$ is a subset of $T$ summing to $u$ then there is a partition $S = (A \cup \{\sum T-2u\}) \cup (T \setminus A)$; indeed, the first part sums to $u + (\sum T-2u) = \sum T-u$, which is what the second part sums to. In other words, if $T$ has a subset summing to $u$, then $S$ can be partitioned into two parts with equal sum.
What about the other direction? Suppose that $S$ can be partitioned into two parts. One of these parts contains $\sum T - 2u$, say $A \cup \{ \sum T - 2u \}$. Since $\sum S = \sum T + (\sum T - 2u) = 2(\sum T - u)$, it follows that $\sum A + T - 2u = \sum T - u$, or $\sum A = u$.
You might be worried that $\sum T - 2u \in T$. I'll let you figure out what to do in this case.