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

Authors:

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 $\mathbb{Q}$$^n$ within arbitrary $n$ > 1. Actually, it is proven that the MASC problem is intractable even if the sets A and B used in its setting being in a general position.

UDC:
519.8