# Prove Partition is NP-Complete using that SubsetSum so is it

The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete.

The Partition problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ can be partitionated in two subsets such that the difference between the sums of the both sets are lesser or equal to $K$.

Prove that the partition problem is NP-Complete using that SubsetSum so is it.

Any ideas?

• Your title asks to prove the SubsetSum problem is NP-complete, while body text asks to prove the Partition problem is NPC. – fade2black Aug 6 '17 at 6:10
• This is a standard exercise, and it is really best that you solve it on your own. We will not be available to help you on your exam. – Yuval Filmus Aug 6 '17 at 6:43
• @YuvalFilmus If i opened this question is because i couldn't solve the exercise. I would appreciate any help. – jscherman Aug 6 '17 at 7:00
• @fade2black yep, my bad. I've already changed it =) – jscherman Aug 6 '17 at 7:01

Define your $PARTITION(S, K)$ problem as:
"Are there partitions $S_1, S_2$ of $S$ such that $|\text{sum}(S_1) - \text{sum}(S_2)| \leq K$, where $\text{sum}(S_i)$ is the sum of all elements of $S_i$?".
Then $PARTITION(S, 0)$ would mean $|\text{sum}(S_1) - \text{sum}(S_2)| \leq 0$ which is true only if $\text{sum}(S_1) = \text{sum}(S_2)$. Thus, given $S$ we could reduce the $SUBSET(S,k)$ problem to the problem asking for existence of two partitions of $S$ with equal sums of elements - $PARTITION(S, 0)$.
Let $s=\text{sum(S)}$ and define a new set $S_{new} = S \cup \{2k − s\}$. We choose $2k-s$ since the sum of $S_{new}$ is $2k-s+s = 2k = k+k$, and we want two partitions with equal sizes equal to $k$.
Now call (reduction!) $PARTITION(S_{new},0)$. If it returns YES/TRUE then $S_{new}$ can be partitioned into two sets $S_1$ and $S_2$ with sums equal to $k$. Also notice that either $S_1$ or $S_2$ can contain the new element $2k − s$ (since they are partitions) meaning that either $S_1$ or $S_2$ is a subset of $S$. Thus we have a subset (without the element $2k − s$) of $S$ with the sum $k$, and we return YES/TRUE. Otherwise, if we get NO/FALSE then return NO/FALSE.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://cs.stackexchange.com/questions/79767/prove-partition-is-np-complete-using-that-subsetsum-so-is-it/79774", "fetch_time": 1558778064000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-22/segments/1558232257939.82/warc/CC-MAIN-20190525084658-20190525110658-00435.warc.gz", "warc_record_offset": 439082925, "warc_record_length": 32697, "token_count": 737, "char_count": 2270, "score": 3.953125, "int_score": 4, "crawl": "CC-MAIN-2019-22", "snapshot_type": "longest", "language": "en", "language_score": 0.8669928312301636, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00031-of-00064.parquet"}