Question

How to proof that the 2-partition problem can be transformed to 3-partition problem and the time complexity of the transformation

(i.e. the 2-partition problem can be solved by using an algorithm that solves the 3-partition problem)

Answer 1

A most common mistake is to believe that the polynomial reduction used is in theory of the complexity to define NP completeness does preserve the strong sense. This is completely false :

By definition of NP-complete, ANY NP-complete problem can be reduced to ANY other NP-complete problem.

A reduction from a NP-complete problem in tre strong sense, say 3-Partition, does not prove that your problem is NP-complete in the strong sense. It simply proves that your problem is NP-complete. In particular there does exist a reduction from 3-PARTITION to PARTITION.

- Conversely a reduction from a NP-complete problem in the ordinary sense does not prevent your problem to be NP complete in the strong sense. In particular there does exist a reduction from PARTITION to 3-PARTITION.

To preserve the strong sense, you need more than the usual reduction. In their book Garey & Johnson define around page 100 the notion of pseudo-polynomial reduction for this purpose. Basically it ensures that in the transformation, the maximum value does not grow exponentially and the size of the encoding is not shrink exponentially.