О вычислительной и аппроксимационной сложности задачи о минимальном аффинном разделяющем комитете

Two сombinatorial problems, Three-elements affine separating committee (3-ASC) and Minimal affine separating committee (MASC), which are closely connected with a training problem in the special case of perceptrons, are considered. It is proven that the former problem is NP - complete and the later is NP -hard and does not belong to Apx. Also some approximation algorithm for the MASC problem is discussed.