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

Jorge A. RUIZ-VANOYE; Joaqun PREZ-ORTEGA; Rodolfo A. PAZOS RANGEL; Ocotln DAZ-PARRA; Hctor J. FRAIRE-HUACUJA; Juan FRAUSTO-SOLS; Gerardo REYES-SALGADO; Laura CRUZ-REYES

doi:10.1631/jzus.C1200349

Your Location：

Home >

Browse articles >

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

计算机与自动化 | Updated：2022-12-09

- Application of formal languages in polynomial transformations of instances between NP-complete problems
- Application of formal languages in polynomial transformations of instances between NP-complete problems
- 信息与电子工程前沿（英文） 2013年14卷第8期页码：623-633
- Affiliations：
  
  1.DACI, Universidad Autnoma del Carmen, Cd. del Carmen 24180, Mexico
  2.Computer Science, Centro Nacional de Investigacin y Desarrollo Tecnolgico, Cuernavaca 62490, Mexico
  3.Systems and Computer Science, Instituto Tecnolgico de Ciudad Madero, Ciudad Madero 89440, Mexico
  4.Informatics, Universidad Politcnica del Estado de Morelos, Jiutepec 62560, Mexico
  5.Computer Science, Instituto Tecnolgico de Cuautla, Cuautla 62745, Mexico
- Author bio：
  
  [ "Jorge A. RUIZ-VANOYE, jorge@ruizvanoye.com" ]
- Funds：
- DOI：10.1631/jzus.C1200349
  中图分类号： TP301.5
- 收稿：2012-12-03，
  
  修回：2013-;7-12，
  
  纸质出版：2013-08
- Accepted：
Scan QR Code
Application of formal languages in polynomial transformations of instances between NP-complete problems[J]. 信息与电子工程前沿（英文）, 2013,14(8):623-633.

Jorge A. RUIZ-VANOYE, Joaqun PREZ-ORTEGA, Rodolfo A. PAZOS RANGEL, et al. Application of formal languages in polynomial transformations of instances between NP-complete problems[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(8): 623-633.
Application of formal languages in polynomial transformations of instances between NP-complete problems[J]. 信息与电子工程前沿（英文）, 2013,14(8):623-633. DOI： 10.1631/jzus.C1200349.

Jorge A. RUIZ-VANOYE, Joaqun PREZ-ORTEGA, Rodolfo A. PAZOS RANGEL, et al. Application of formal languages in polynomial transformations of instances between NP-complete problems[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(8): 623-633. DOI： 10.1631/jzus.C1200349.

摘要

Abstract

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

to another problem

. This extrapolation could be useful for predicting the performance of an algorithm for solving

based on its known performance for problem

or for taking an algorithm that solves

and adapting it to solve

关键词

Keywords

references

A.V. Aho , , , R. Sethi , , , J.D. Ullman . . Compilers: Principles . . Techniques, and Tools. Addison-Wesley, USA , , 1986 . . p.14 - - 16 . . . .

J.W. Backus . . The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich Association for Computing Machinery (ACM) and the Association for Applied Mathematics and Mechanics (GAMM) Conference . . Proc. Int. Conf. on Information Processing , , 1959 . . p.125 - - 132 . . . .

J. Bao , , , L.J. Zhou , , , Y. Yan . . Analysis on complexity of neural networks using integer weights . . Appl. Math. Inf. Sci. , , 2012 . . 6 317 - - 323 . . . .

J.H. Bennett . . On Spectra . . PhD Thesis, Princeton University, USA. , , 1962 . . .

C.H. Bennett , , , G. Brassard , , , R. Jozsa , , , D. Mayers , , , A. Peres , , , B. Schumacher , , , W.K. Wootters . . Reduction of quantum entropy by reversible extraction of classical information . . J. Mod. Opt. , , 1994 . . 41 ( ( 12 ): ): 2307 - - 2314 . . DOI: 10.1080/09500349414552161 http://doi.org/10.1080/09500349414552161 . .

J.C. Brown . . Loglan . . Sci. Am. , , 1960 . . 202 53 - - 63 . . DOI: 10.1038/scientificamerican0660-53 http://doi.org/10.1038/scientificamerican0660-53 . .

A. Cobham . . The Intrinsic Computational Difficulty of Functions . . Proc. Congress for Logic, Mathematics, and Philosophy of Science , , 1964 . . p.24 - - 30 . . . .

S.A. Cook . . The Complexity of Theorem Proving Procedures . . Proc. 3rd ACM Symp. on Theory of Computing , , 1971 . . p.151 - - 158 . . . .

S.A. Cook . . An overview of computational complexity . . Commun. ACM , , 1983 . . 26 ( ( 6 ): ): 400 - - 408 . . DOI: 10.1145/358141.358144 http://doi.org/10.1145/358141.358144 . .

D. Deutsch . . Quantum computational networks . . Proc. R. Soc. Lond. A , , 1989 . . 425 ( ( 1868 ): ): 73 - - 90 . . DOI: 10.1098/rspa.1989.0099 http://doi.org/10.1098/rspa.1989.0099 . .

J. Edmonds . . Paths, trees, and flowers . . Canad. J. Math. , , 1965 . . 17 449 - - 467 . . DOI: 10.4153/CJM-1965-045-4 http://doi.org/10.4153/CJM-1965-045-4 . .

M.R. Garey , , , D.S. Johnson . . Computers and Intractability: a Guide to the Theory of NP-Completeness . . W.H. Freeman and Company, New York , , 1979 . . p.1 - - 10 . . . .

J. Hartmanis , , , R.E. Stearns . . On the computational complexity of algorithms . . Trans. Am. Math. Soc. , , 1965 . . 117 ( ( 5 ): ): 285 - - 306 . . DOI: 10.1090/S0002-9947-1965-0170805-7 http://doi.org/10.1090/S0002-9947-1965-0170805-7 . .

J. Hopcroft , , , J. Ullman . . Formal Languages and Their Relation to Automata . . Addison-Wesley, USA , , 1969 . . p.1 - - 7 . . . .

P. Jonsson , , , C. Bäckström . . Complexity Results for State-Variable Planning under Mixed Syntactical and Structural Restriction . . Proc. 6th Int. Conf. on Artificial Intelligence: Methodology, Systems, Applications , , 1994 . . p.205 - - 213 . . . .

R.M. Karp . . Reducibility among Combinatorial Problems . . In: Miller R.E., Thatcher, J.W. (Eds.), Complexity of Computer Computations. Plenum Press, New York , , 1972 . . p.85 - - 104 . . DOI: 10.1007/978-1-4684-2001-2_9 http://doi.org/10.1007/978-1-4684-2001-2_9 . .

A.N. Kolmogorov . . Three approaches to the quantitative definition of information . . Prob. Inf. Transm. , , 1965 . . 1 1 - - 7 . . . .

J. Levine . . Flex & Bison . . O′Reilly Media, USA. , , 2009 . . .

S. Martello , , , P. Toth . . Knapsack Problems: Algorithms and Computer Implementations . . John Wiley & Sons, England , , 1991 . . p.221 - - 236 . . . .

P. Orponen . . On the Instance Complexity of NP-Hard Problems . . Proc. 5th Annual Structure in Complexity Theory Conf. , , 1990 . . p.20 - - 27 . . DOI: 10.1109/SCT.1990.113951 http://doi.org/10.1109/SCT.1990.113951 . .

C. Papadimitriou , , , K. Steiglitz . . Combinatorial Optimization: Algorithms and Complexity . . Prentice-Hall, New Jersey , , 1982 . . p.342 - - 357 . . . .

C.H. Papadimitriou . . Computational Complexity . . Addison-Wesley, UK , , 1994 . . p.260 - - 265 . . . .

M.O. Rabin . . Speed of Computation and Classification of Recursive Sets . . Third Convention of Scientific Societies , , 1959 . . p.1 - - 2 . . . .

J.A. Ruiz-Vanoye , , , O. Daz-Parra . . An overview of the theory of instances computational complexity . . Int. J. Combin. Optim. Probl. Inf. , , 2011 . . 2 ( ( 2 ): ): 21 - - 27 . . . .

J.A. Ruiz-Vanoye , , , O. Daz-Parra , , , J. Prez-Ortega , , , R.A. Pazos , , , G. Reyes Salgado , , , J.J. Gonzlez-Barbosa . . Complexity of Instances for Combinatorial Optimization Problems . . In: Al-Dahoud, A. (Ed.), Computational Intelligence & Modern Heuristics, Chapter 19. IN-TECH Education and Publishing , , 2010 . . p.319 - - 330 . . DOI: 10.5772/7807 http://doi.org/10.5772/7807 . .

J.A. Ruiz-Vanoye , , , J. Prez-Ortega , , , R.A. Pazos , , , O. Daz-Parra , , , J. Frausto-Sols , , , H.J. Fraire-Huacuja , , , L. Cruz-Reyes , , , J.A. Martnez-Flores . . Survey of polynomial transformations between NP-complete problems . . J. Comput. Appl. Math. , , 2011 . . 235 ( ( 16 ): ): 4851 - - 4865 . . DOI: 10.1016/j.cam.2011.02.018 http://doi.org/10.1016/j.cam.2011.02.018 . .

C.E. Shannon . . The mathematical theory of communication . . Bell Syst. Techn. J. , , 1948 . . 27 ( ( 3 ): ): 379 - - 423 . . DOI: 10.1002/j.1538-7305.1948.tb01338.x http://doi.org/10.1002/j.1538-7305.1948.tb01338.x . .

M. Sipser . . A Complexity Theoretic Approach to Randomness . . Proc. 15th ACM Symp. on Theory of Computing , , 1983 . . p.330 - - 335 . . . .

R. Solomonoff . . A Preliminary Report on a General Theory of Inductive Inference . . Report Ⅴ-131, Zator Co., Cambridge, MA. , , 1960 . . .

R. Solomonoff . . A formal theory of inductive inference. Part Ⅰ . . Inf. Control , , 1964a . . 7 ( ( 1 ): ): 1 - - 22 . . DOI: 10.1016/S0019-9958(64)90223-2 http://doi.org/10.1016/S0019-9958(64)90223-2 . .

R. Solomonoff . . A formal theory of inductive inference. Part Ⅱ . . Inf. Control , , 1964b . . 7 ( ( 2 ): ): 224 - - 254 . . DOI: 10.1016/S0019-9958(64)90131-7 http://doi.org/10.1016/S0019-9958(64)90131-7 . .

L.J. Stockmeyer . . Classifying the Computational Complexity of Problems . . Research Report RC 7606, Mathematical Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, NY. , , 1979 . . .

J.F. Traub , , , G.W. Wasilkowski , , , H. Woźniakowski . . Information-Based Complexity , , : : New York Academic Press , , 1988 . . .

A.M. Turing . . On computable numbers, with an application to the Entscheidungsproblem . . Proc. Lond. Math. Soc. , , 1937 . . s2-42 ( ( 1 ): ): 230 - - 265 . . DOI: 10.1112/plms/s2-42.1.230 http://doi.org/10.1112/plms/s2-42.1.230 . .

H. Wozniakowski . . Survey of information-based complexity . . J. Compl. , , 1985 . . 1 ( ( 1 ): ): 11 - - 44 . . DOI: 10.1016/0885-064X(85)90020-2 http://doi.org/10.1016/0885-064X(85)90020-2 . .

A.C. Yao . . Quantum Circuit Complexity . . Proc. 34th Annual IEEE Symp. on Foundations of Computer Science , , 1993 . . p.352 - - 361 . . . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据