Алгоритмічна складність задачі навчання двопорогових нейронів
Розглядаються питання, пов’язані з розпізнаванням скінченних множин за допомогою двопорогових нейронних елементів. Показано, що задача навчання ДНЕ є 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.