УДК 519.714

О сложности информационных сетей глубины 2 / Д. Ю. Черухин. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. № 1. С. 16-19.

Доказывается нижняя оценка \Omega(n\log_2 n) для сложности произвольной информационной сети глубины 2 с n входами и n выходами, у которой входы независимы, выходы независимы и общая информация любого входа и любого выхода в n раз меньше энтропии любого входа или выхода. В качестве следствия устанавливается аналогичная оценка для булевых схем из функциональных элементов глубины 2.

Библиогр. 5.

К оглавлению номера  Go!