Full Text:   <2586>

Summary:  <1886>

CLC number: TP301.5

On-line Access: 2013-08-02

Received: 2012-12-03

Revision Accepted: 2013-03-19

Crosschecked: 2013-07-12

Cited: 2

Clicked: 6284

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2013 Vol.14 No.8 P.623-633

http://doi.org/10.1631/jzus.C1200349


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


Author(s):  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

Affiliation(s):  DACI, Universidad Autnoma del Carmen, Cd. del Carmen 24180, Mexico; more

Corresponding email(s):   jorge@ruizvanoye.com

Key Words:  Formal languages, Polynomial transformations, NP-completeness


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. Application of formal languages in polynomial transformations of instances between NP-complete problems[J]. Journal of Zhejiang University Science C, 2013, 14(8): 623-633.

@article{title="Application of formal languages in polynomial transformations of instances between NP-complete problems",
author="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",
journal="Journal of Zhejiang University Science C",
volume="14",
number="8",
pages="623-633",
year="2013",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1200349"
}

%0 Journal Article
%T Application of formal languages in polynomial transformations of instances between NP-complete problems
%A Jorge A. Ruiz-Vanoye
%A Joaqun Prez-Ortega
%A Rodolfo A. Pazos Rangel
%A Ocotln Daz-Parra
%A Hctor J. Fraire-Huacuja
%A Juan Frausto-Sols
%A Gerardo Reyes-Salgado
%A Laura Cruz-Reyes
%J Journal of Zhejiang University SCIENCE C
%V 14
%N 8
%P 623-633
%@ 1869-1951
%D 2013
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1200349

TY - JOUR
T1 - Application of formal languages in polynomial transformations of instances between NP-complete problems
A1 - Jorge A. Ruiz-Vanoye
A1 - Joaqun Prez-Ortega
A1 - Rodolfo A. Pazos Rangel
A1 - Ocotln Daz-Parra
A1 - Hctor J. Fraire-Huacuja
A1 - Juan Frausto-Sols
A1 - Gerardo Reyes-Salgado
A1 - Laura Cruz-Reyes
J0 - Journal of Zhejiang University Science C
VL - 14
IS - 8
SP - 623
EP - 633
%@ 1869-1951
Y1 - 2013
PB - Zhejiang University Press & Springer
ER -
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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

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

[2]Backus, J.W., 1959. 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, p.125-132.

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

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

[5]Bennett, C.H., Brassard, G., Jozsa, R., Mayers, D., Peres, A., Schumacher, B., Wootters, W.K., 1994. Reduction of quantum entropy by reversible extraction of classical information. J. Mod. Opt., 41(12):2307-2314.

[6]Brown, J.C., 1960. Loglan. Sci. Am., 202:53-63.

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

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

[9]Cook, S.A., 1983. An overview of computational complexity. Commun. ACM, 26(6):400-408.

[10]Deutsch, D., 1989. Quantum computational networks. Proc. R. Soc. Lond. A, 425(1868):73-90.

[11]Edmonds, J., 1965. Paths, trees, and flowers. Canad. J. Math., 17:449-467.

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

[13]Hartmanis, J., Stearns, R.E., 1965. On the computational complexity of algorithms. Trans. Am. Math. Soc., 117(5):285-306.

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

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

[16]Karp, R.M., 1972. Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (Eds.), Complexity of Computer Computations. Plenum Press, New York, p.85-104.

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

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

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

[20]Orponen, P., 1990. On the Instance Complexity of NP-Hard Problems. Proc. 5th Annual Structure in Complexity Theory Conf., p.20-27.

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

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

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

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

[25]Ruiz-Vanoye, J.A., Díaz-Parra, O., Pérez-Ortega, J., Pazos, R.A., Reyes Salgado, G., González-Barbosa, J.J., 2010. Complexity of Instances for Combinatorial Optimization Problems. In: Al-Dahoud, A. (Ed.), Computational Intelligence & Modern Heuristics, Chapter 19. IN-TECH Education and Publishing, p.319-330.

[26]Ruiz-Vanoye, J.A., Pérez-Ortega, J., Pazos R.A., Díaz-Parra, O., Frausto-Solís, J., Fraire-Huacuja, H.J., Cruz-Reyes, L., Martínez-Flores, J.A., 2011. Survey of polynomial transformations between NP-complete problems. J. Comput. Appl. Math., 235(16):4851-4865.

[27]Shannon, C.E., 1948. The mathematical theory of communication. Bell Syst. Techn. J., 27(3):379-423.

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

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

[30]Solomonoff, R., 1964a. A formal theory of inductive inference. Part I. Inf. Control, 7(1):1-22.

[31]Solomonoff, R., 1964b. A formal theory of inductive inference. Part II. Inf. Control, 7(2):224-254.

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

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

[34]Turing, A.M., 1937. On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc., s2-42(1):230-265.

[35]Wozniakowski, H., 1985. Survey of information-based complexity. J. Compl., 1(1):11-44.

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

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE