Параллельные вычисления и комитетные конструкции

Статья содержит исторический обзор результатов, подтверждающих глубинную связь между параллельными вычислениями и процедурами обучения слоистых нейронных сетей, одной из формализаций которых является теория комитетных конструкций. Кроме того, рассматриваются две комбинаторные задачи, связанные с обучением распознаванию образов в классе аффинных комитетов: задача проверки существования аффинного разделяющего комитета из трех элементов (3-ASC) и задача о минимальном по числу элементов аффинном разделяющем комитете (MASC). Показано, что задача 3-ASC $NP$-полна, а задача MASC $NP$-трудна и не принадлежит классу Apx.