NP-completeness of some problems of choosing a vector subset

Abstract

The NP-completeness is proved of some problems of choosing a Euclidean vector subset. One of the data analysis problems is reduced to these problems. The required subset is assumed to have a fixed cardinality and include the vectors that are “close” to each other by the criterium of the minimum sum of squares of distances.