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

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