7
$\begingroup$

The partition problem is a well-known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers, and we want to decide the existence of a partition into two sets that have the same sum. My question is:

Is the partition problem still NP-complete if all input integers are distinct (i.e., no integer is repeated)?

$\endgroup$
11
$\begingroup$

Here is an outline of a reduction from PARTITION to UNIQUE PARTITION. Suppose the original numbers are $x_1,\ldots,x_n$ and the target is $T$. I assume that all $x_i$ are positive integers. The new numbers are going to be $2^n x_i + i$, as well as $1,2,4,\ldots,2^{n/2}$, and the new target is $2^n T + 2^{n/2}$. (The numbers $2^n,2^{n/2}$ are quite arbitrary and could be made much smaller.)

$\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.