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

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.