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

Институт математики и механики УрО РАН, Екатеринбург, Россия

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

Литература:

Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете и смежных задач // ДАН, 2006. - 406. - №6. - С. 742-745.
Хачай М.Ю. О вычислительной и аппроксимационной сложности задачи о минимальном аффинном разделяющем комитете // Таврический вестник информатики и математики. 2006. - №1. - С.34–43.
Megiddo N., Tamir A. On the complexity of locating linear facilities in the plane // Operations research letters. 1982. - Vol. 1. - No. 5. - P. 194-197.
Megiddo N. On the complexity of polyhedral separability // Discrete and Computational Geometry. 1988. – 3. - P. 325-337.
Blum A.L., Rivest R.L. Training a 3-node Neural Network is NP-complete // Neural Networks. 1992. - Vol. 5. - P. 117–127.
Lin J.H., Vitter J.S. Complexity Results on Learning by Neural Nets // Machine Learning. 1991. - Vol 6. – P. 211–230.
Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика. 1971. - №3. - С. 140–146.
Mazurov Vl.D., Khachai M.Yu., Rybin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction. {\it Proceedings of the Steklov Institute of mathematics}. Suppl. 1, (2002), S67–S101.
Dinur I., Regev O. and Smyth C. The hardness of 3-uniform hypergraph coloring. In: Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November 2002.