stuck pier
I'm trying to prove that the BinPacking problem is NP hard granted the partition problem* is NP hard. * If I have E a set of positive integers, can I find two subsets such that the sum of the integers in both subsets are equal.
The polynomial reduction I found would be the following:
- My objects O are defined as what's in E (the weight of each object is the integer value and |E| is the number of objects)
- Number of bags = 2
- Capacity of each bag is half of the sum of everything in E
Is this wrong because my polynomial reduction only reduces to BinPacking with 2 bags whose capacity are the same?
I’m skeptic because if I carry out this proof, and I find an algorithm in polynomial time for the partition problem I will only have proof that BinPacking with 2 bags whose capacity are the same is solvable in a polynomial time.
deft forum