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

Журнал: 
Страница: 
218
УДК: 
519.8
В работе показано, что задача о минимальном аффинном разделяющем комитете (JNIASC), тесно связанная с процедурой обучения распознаванию в классе полиэдральных решающих правил, остается труднорешаемой, даже будучи сформулированной в пространстве произвольной фиксированной размерности n > 1, причем труднорешаемость задачи не обусловлена вырожденностью разделяемых множеств.
info_eng: 
The paper presents new results on computational complexity of the known Minimum Affine Separating Committee (MASC) combinatorial optimization problem that is closely connected with the problem of optimal learning for perceptrons. It is proved that the MASC problem remains intractable being formulated in Q*n within arbitrary n > 1. Actually, it is proven that the MASC problem is intractable even if the sets A and В used in its setting being in a general position.