Application of formal languages in polynomial transformations of instances between NP-complete problems  

作　　者：Jorge A. RUIZ-VANOYE Joaquín PREZ-ORTEGA Rodolfo A. PAZOS RANGEL Ocotlán DíAZ-PARRA Héctor J. FRAIRE-HUACUJA Juan FRAUSTO-SOLíS Gerardo REYES-SALGADO Laura CRUZ-REYES 

机构地区：[1]DACI,Universidad Autónoma del Carmen [2]Computer Science,Centro Nacional de Investigación y Desarrollo Tecnológico [3]Systems and Computer Science,Instituto Tecnológico de Ciudad Madero [4]Informatics,Universidad Politécnica del Estado de Morelos [5]Computer Science,Instituto Tecnológico de Cuautla

出　　处：《Journal of Zhejiang University-Science C(Computers and Electronics)》2013年第8期623-633,共11页浙江大学学报C辑（计算机与电子（英文版）

摘　　要：We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson's. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transforma- tions, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson＇s. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.

关 键 词：Formal languages Polynomial transformations NP-COMPLETENESS 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]