%0 Journal Article %1 MJOR5 %A Pazos R., Rodolfo A. %A Pérez O, Joaquín %A Ong C., Ernesto %A Mexicano, Adriana %A Zavala-Díaz, José C. %D 2012 %J Mexican Journal of Operations Research %K algorithm genetic optimal ordering transfer %N 1 %P 45-54 %T Paradox of the Transformation between the Partition and the Bin Packing Problems %U http://mjor.org/ojs/index.php?journal=MJOR&page=article&op=view&path%5B%5D=5 %V 1 %X The NP-completeness theory provides a method for telling whether a decision/optimization problem is ëasy\" (i.e., it belongs to the P class) or \"hard\" (i.e., it belongs to the NP-complete class). Many famous problems have been proven to belong to the NP-complete class such as the Traveling Salesman problem, the Bin Packing problem, the Knapsack problem, etc. This paper deals with a usually overlooked property of NP-complete problems: the bi-directionality of the transformation between pairs of NP-complete problems. This property states that for any two NP-complete problems A and B, it must be possible to transform A to B in polynomial time and vice versa. This article shows that this property does not seem to hold for two NP-complete problems: Partition and Bin Packing, which contradicts the theory and, therefore, constitutes the paradox, subject of this paper.

@article{MJOR5, abstract = {The NP-completeness theory provides a method for telling whether a decision/optimization problem is \"easy\" (i.e., it belongs to the P class) or \"hard\" (i.e., it belongs to the NP-complete class). Many famous problems have been proven to belong to the NP-complete class such as the Traveling Salesman problem, the Bin Packing problem, the Knapsack problem, etc. This paper deals with a usually overlooked property of NP-complete problems: the bi-directionality of the transformation between pairs of NP-complete problems. This property states that for any two NP-complete problems A and B, it must be possible to transform A to B in polynomial time and vice versa. This article shows that this property does not seem to hold for two NP-complete problems: Partition and Bin Packing, which contradicts the theory and, therefore, constitutes the paradox, subject of this paper.}, added-at = {2012-04-29T06:43:25.000+0200}, author = {Pazos R., Rodolfo A. and Pérez O, Joaquín and Ong C., Ernesto and Mexicano, Adriana and Zavala-Díaz, José C.}, biburl = {https://www.bibsonomy.org/bibtex/24c0ff06fee6b6208215733b57ea88b61/mjor}, interhash = {9717a1f3179da1f233079da174bf5979}, intrahash = {4c0ff06fee6b6208215733b57ea88b61}, journal = {Mexican Journal of Operations Research}, keywords = {algorithm genetic optimal ordering transfer}, number = 1, pages = {45-54}, timestamp = {2012-04-29T06:43:25.000+0200}, title = {Paradox of the Transformation between the Partition and the Bin Packing Problems}, url = {http://mjor.org/ojs/index.php?journal=MJOR&page=article&op=view&path%5B%5D=5}, volume = 1, year = 2012 }