Author/Authors :
Jorge A. Ruiz-Vanoye، نويسنده , , Jorge A. and Pérez-Ortega، نويسنده , , Joaquيn and Pazos R.، نويسنده , , Rodolfo A. and Dيaz-Parra، نويسنده , , Ocotlلn and Frausto-Solيs، نويسنده , , Juan and Fraire Huacuja، نويسنده , , Hector J. and Cruz-Reyes، نويسنده , , Laura and Martيnez F.، نويسنده , , José A.، نويسنده ,
Abstract :
This paper aims at being a guide to understand polynomial transformations and polynomial reductions between NP-complete problems by presenting the methodologies for polynomial reductions/transformations and the differences between reductions and transformations. To this end the article shows examples of polynomial reductions/transformations and the restrictions to reduce/transform between NP-complete problems. Finally, this paper includes a digraph with the historical reductions/transformations between instances of NP-complete problems and introduces the term family of polynomial transformations.
