Computational Methods in Discrete Mathematics

Computational complexity of the synthesis of composite models for Lipschitz-bounded functions

I. S. Kalinnikov

National Research University of Electronic Technology, Moscow, Russia

Abstract: 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.

UDC: 510.52