Вычислительная сложность задачи выбора типичных представителей в конечном множестве точек метрического пространства

Исследуется сложностной статус одной экстремальной задачи выбора подмножества $p$ наиболее типичных точек в заданном конечном множества точек метрического пространства. При этом требуется, чтобы выбранное подмножество наилучшим образом описывало исходное множество с точки зрения некоторого геометрического критерия. Рассматриваемая задача является формализацией одной прикладной проблемы из анализа данных, заключающейся в отыскании подмножества типичных представителей выборки с опорой на функцию конкурентного сходства. В статье доказывается, что рассматриваемая задача NP-трудна. Для этого к ней полиномиально сводится одна из NP-трудных задач  — задача о трёхмерном сочетании. Ил. 1, библиогр. 14.