1
$\begingroup$

I am not quite sure howto define SET-PARTITION as a language as in Sipser. Is it

$$ \left\{ \langle S,A,B\rangle \;\middle|\; (A,B) \text{ is partition of } S \text{ and } \sum_{n\in A} n = \sum_{n\in B} n \right\} \quad \text{ or } \\ \left\{ \langle S\rangle \;\middle|\; \text{ there exists a partition } (A,B) \text{ of } S \text{ with } \sum_{n\in A} n = \sum_{n\in B} n\right\} \quad ? $$

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Hint: SET-PARTITION is hard for NP, i.e. most likely there is no polynomial algorithm. But one of your two formulations has a very easy polynomial algorithm. As a side note: This implies that SET-PARTITION is in NP. $\endgroup$
    – ttnick
    Commented May 25, 2020 at 12:14

1 Answer 1

Reset to default
1
$\begingroup$

The set partition problem asks whether there exists a 2-partition of a multi-set such that sum of numbers in one set is equal to the sum of numbers in the other set.

Note the phrase whether there exists; if you are already being given the partition in the input $\langle S,A,B \rangle$ then the problem becomes whether the given partition is valid and sum of elements of $A$ and $B$ are equal. This problem is easy and can be solved in polynomial it time.

However, Set Partition is NP-Complete, which seems unlikely to be solved in polynomial time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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