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

Рассматриваются две комбинаторных задачи, связанные с обучением распознаванию образов: задача проверки существования аффинного разделяющего комитета из 3-х элементов (3-А8С) и задача о минимальном по числу элементов аффинном разделяющем комитете (МА8С). Показано, что задача 3-А8С ЖР-полна, а задача МА8С .ЛГР-трудна и не принадлежит классу Арх. Обсуждается новый приближенный алгоритм для задачи МА8С.