Geodesic
Computational complexity of the synthesis of composite models for Lipschitz-bounded functions
Prikladnaâ diskretnaâ matematika, no. 3 (2014), pp. 103-110.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is devoted to the analysis of computational complexity of the synthesis of composite models for Lipschitz-bounded surjective functions of single variable. Composite models are some function approximation methods based on approximating via composition of functions taken from a given set. In this paper, it is proved that the problem of building strictly optimal composite model for a target functions via a given set of functions is NP-complete. Methods that are capable to build a near-optimal composition model are discussed. Some of these methods can be realized as algorithms with the polynomial computational complexity but they have a limited application.
Keywords: function composition, composition models, NP-completeness, Lipschitz-bounded, computational complexity. 
@article{PDM_2014_3_a9,
     author = {I. S. Kalinnikov},
     title = {Computational complexity of the synthesis of composite models for {Lipschitz-bounded} functions},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {103--110},
     publisher = {mathdoc},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_3_a9/}
}
TY  - JOUR
AU  - I. S. Kalinnikov
TI  - Computational complexity of the synthesis of composite models for Lipschitz-bounded functions
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 103
EP  - 110
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_3_a9/
LA  - ru
ID  - PDM_2014_3_a9
ER  - 
%0 Journal Article
%A I. S. Kalinnikov
%T Computational complexity of the synthesis of composite models for Lipschitz-bounded functions
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 103-110
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2014_3_a9/
%G ru
%F PDM_2014_3_a9
I. S. Kalinnikov. Computational complexity of the synthesis of composite models for Lipschitz-bounded functions. Prikladnaâ diskretnaâ matematika, no. 3 (2014), pp. 103-110. http://geodesic.mathdoc.fr/item/PDM_2014_3_a9/

[1] Koza J. R., Genetic Programming: on the Programming of Computers by Means of Natural Selection, A Bradford Book, London, 1998, 815 pp.

[2] Luke S., Esentials of metaheuristics, , 2009 http://cs.gmu.edu/~sean/book/metaheuristics

[3] Labutin S. A., Pugin M. V., Analiz signalov i zavisimostei, Ucheb. posobie, Nizhegorod. gos. tekh. un-t, N. Novgorod, 2001, 158 pp.

[4] Seong J. K., Elber G., Kim M. S., Polynomial decomposition and its applications, , 2003 http://cana.kaist.ac.kr/seong/decomposition.pdf

[5] Karp R. M., “Reducibility among combinatorial problems”, GJ-474 report, 1971, 87–103 http://www.seas.upenn.edu/~bhusnur4/cit596_spring2014/karp-1971.pdf | MR

[6] Papadimitriu X. X., Staiglits K., Kombinatornaya optimizatsiya: Algoritmy i slozhnost, Mir, M., 1987, 520 pp. | MR

[7] Even S., Goldreich O., “The minimum-length generator sequence problem is NP-hard”, J. Algorithms, 2 (1981), 311–313 | DOI | MR | Zbl

[8] Alonso C., Gutierrez J., Recio T., “A rational function decomposition algorithm by near-separated polynomials”, J. Symbolic Comput., 19 (1995), 527–544 | DOI | MR | Zbl

[9] Kalinnikov I. S., “Algoritm postroeniya dekompozitsii nepreryvnoi funktsii odnogo argumenta po zadannomu mnozhestvu funktsii”, Innovatsii v nauke, obrazovanii i biznese, Kh Mezhdunar. nauchn. konf., Ch. 2, KGTU, Kaliningrad, 2012, 160–163

[10] Chavez E., Navarro G., Baeza-Yates R., Marroquin J. L., “Search in metric spaces”, ACM Computing Surveys, 33:3 (2001), 273–321 | DOI | MR

[11] Zezula P., Amato G., Dohnal V., Batko M., Similarity Search: The Metric Space Approach, Springer Verlag, N.Y., 2006, 220 pp. | Zbl

[12] Rastrigin L. A., Ripa K. K., Tarasenko G. S., Adaptatsiya sluchainogo poiska, Zinatne, Riga, 1978, 243 pp. | MR | Zbl

[13] Alenberg L., “The schema theorem and Price's theorem”, Foundations of Genetic Algorithms, 3, Morgan Kaufmann, San Francisco, 1995, 23–49 | DOI