Алгоритмічна складність задачі навчання двопорогових нейронів

Abstract

Розглядаються питання, пов’язані з розпізнаванням скінченних множин за допомогою двопорогових нейронних елементів. Показано, що задача навчання ДНЕ є NP-повною. Також наведено умови, виконання яких забезпечує двопороговість булевих функцій, які задаються за допомогою списків рішень. We study finite set dichotomies on bithreshold neurons. We prove that training a BN is NP-complete task. We also give sufficient conditions ensuring that decision list represents a bithreshold function.