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 split it into two subsets such that the sums 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.
It is pleasantly surprising that you got a simple reduction from the partition problem to the BinPacking problem. Instead of being skeptic, you are supposed to celebrate your elegant proof.
Here is a little lemma for this occasion.
Let us represent a decision problem by $(I, Y)$, where $I$ is an infinite set of inputs and $Y\subseteq I$ is the subset of inputs for which the answer is YES.
(All is at least as hard as a part) Lemma: Let $I^-\subseteq I$. If $(I^-, Y\cap I^-)$ is NP-hard, so is $(I,Y)$.
Proof: Obvious. (Please make sure you can prove it rigorously.)
Since you have proved the partial BinPacking problem, which is with 2 bags whose capacity are the same is NP-hard, so is the whole BinPacking problem.
If we only deduce in term of NP-hardness, a polynomial-time algorithm for the partition problem would imply "that BinPacking with 2 bags whose capacity are the same is solvable in a polynomial time" only. It does not imply the existence of a polynomial-time algorithm for the (whole) BinPacking problem.
However, since the partition problem is NP-complete and (the decision version of) the BinPacking problem is a NP-problem, a polynomial-time algorithm for the partition problem will immediately gives a polynomial-time algorithm for the BinPacking problem once we integrate with a polynomial-time reduction of the BinPacking problem to the partition problem.
What you see here is a very general phenomenon.
In fact, people have been researching intensively, for an NP-hard problem $(I,Y)$, how much smaller $I^-$ can be so that $(I^-, Y\cap I^-)$ remains NP-hard. A very small such $I'$ will illustrate where the NP-hardness of $(I, Y)$ comes from. Here we can say that the NP-hardness of BinPacking problem is already present in the much smaller case of two bags with equal capacity.
When $I^-$ becomes smaller enough, it may happen that it is "hard" to compute the YES/NO answer to most large elements of $I^-$. We could then say $I^-$ are hard instances of $I$. You can take a look at Hard instances and phase-transition.