- About EITEE
- Articles Online
- For Authors
- For Reviewers
- Features
- Subscription & Service
- Personal Center
- Logout
FOLLOWUS
- About EITEE
- Introduction
- Editorial Board
- Corresponding Experts
- Events
- Honors
- Contact Us
- Articles Online
- Current Issue
- Archive
- Special Issues
- Virtual Issues
- Highlights
- In Press
- For Authors
- Submit
- Call for papers
- Guide for Authors
- Ethics & Disclosures
- Fee & Funding
- Downloads
- For Reviewers
- Guide for Reviewers
- Ethics & Disclosures
- Thanks card
- Features
- FITEE Forum
- Engineering Front
- Paper Videos
- Editors’ Corner
- Other Resources
- Subscription & Service
- Subscription
- Services
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
- Frontiers of Information Technology & Electronic Engineering Vol. 14, Issue 8, Pages: 623-633(2013)
- 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
CLC： TP301.5Received：03 December 2012，
Revised：2013-;7-12，
Published：2013-08
- Accepted：
Scan QR Code
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.
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
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
.
关键词
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 . . . .
- L-PDFDownload
- Meta-XMLDownload
- BibTeXDownload
- EndnoteDownload
- RefMan Download
- NoteExpressDownload
- NoteFirstDownload
Publicity Resources
Related Articles
Related Author
Related Institution
Chat- Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
- Tel：+86-571-88273162 Email：fitee@zju.edu.cn
- Copyright © 2000 - 2025, Zhejiang University Press 京ICP备09064830号-19
京公网安备11010802024621 - It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
- Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
