Об одном варианте задачи выбора подмножества векторов

Доказана NP-полнота задачи выбора подмножества “похожих” векторов, к которой сводится один из вариантов проблемы апостериорного (off-line) помехоустойчивого обнаружения в числовой последовательности неизвестного повторяющегося вектора в случае, когда помеха аддитивна. Обоснован приближённый полиномиальный алгоритм решения этой задачи с гарантированной оценкой точности в случае фиксированной размерности пространства. Библиогр. 13.