Garey and Johnson describe in their book many NP-complete problems which are based on sets, for example Hitting Set, Minimum Test Set, Set Packing, Set Splitting, and many more.

The traditional mathematical definition of a set does not allow duplicates; when multiplicities count, the object is called a multiset.

Are the sets in the NP-complete problems described by Garey and Johnson allowed to contain duplicates?


1 Answer 1


It doesn't matter. If a certain problem has one version in which the encoding of sets allows for repeated elements (which are ignored semantically), and another in which repeated elements are forbidden, then there is a simple polynomial time reduction from the former to the latter showing that if the first version is NP-complete, so is the second one.


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.