Let S = {(1,... an} and let f: S +2+ (that is, f maps elements of S to the positive integers). A partition of S is a pai

[answerhappygod]

Let S 1 An And Let F S 2 That Is F Maps Elements Of S To The Positive Integers A Partition Of S Is A Pai 1 (26.33 KiB) Viewed 38 times

Let S = {(1,... an} and let f: S +2+ (that is, f maps elements of S to the positive integers). A partition of S is a pair of sets A, B such that S = AU B and AnB = 0. The Partition Problem asks if there exists a partition of Sinto sets A, B such that f(x) = f(r) ZEA TEB Notice that while this definition of the problem looks weird, it's written in this way in order to permit us to have multiple items with the same value, that is a "multiset" of numbers. Prove that Partition is NP-hard.