-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you have to reduce from subset sum, or are you OK with reduction from any NP-complete problem? $\endgroup$ – TCSGrad May 7 '14 at 1:51
  • $\begingroup$ 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. $\endgroup$ – user119264 May 7 '14 at 1:58
  • $\begingroup$ Try writing your solution in words. It's very hard to follow the way it's presented now. $\endgroup$ – Yuval Filmus May 7 '14 at 3:56
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – Raphael May 7 '14 at 7:45
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.