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

В работах [1, 2] получены результаты по вычислительной и аппроксимационной сложности задачи MASC о минимальном аффинном разделяющем комитете для конечных множеств A, B  Q". В частности, показано, что эта задача NP трудна и не принадлежит классу Apx (в предположении, что P ≠ NP). Тем не менее, открытыми оставались вопросы получения оценок порога ее эффективной аппроксимируемости и оценки вычислительной сложности ряда важных для приложений частных случаев задачи, получаемых наложением дополнительных ограничений, например, фиксации размерности пространства. В настоящей статье приводится нижняя оценка порога полиномиальной аппроксимируемости задачи в общем случае и обосновывается труднорешаемость задачи в пространствах фиксированной размерности, большей единицы. В частности, показывается, что задача о комитетной отделимости остается труднорешаемой, даже будучи сформулированной на плоскости (т. е. в наиболее простом нетривиальном случае). Справедливость этого факта следует из полиномиальной сводимости к исследуемой задаче известной задачи PC о покрытии прямыми конечного множества на плоскости, труднорешаемость которой доказана [3]. Методика сведения представляет собой модификацию методики, описанной в [4], использовавшейся в этой работе для обоснования труднорешаемости задачи о кусочно-линейной отделимости конечных множеств на плоскости.