Д. Ю. Черухин, “Нижняя оценка сложности в классе схем глубины $2$ без ограничений на базис”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2005, номер 4,страницы 54

Эта публикация цитируется в 1 статье

Краткие сообщения

Нижняя оценка сложности в классе схем глубины $2$ без ограничений на базис

Д. Ю. Черухин

Аннотация: Рассмотрены схемы из функциональных элементов глубины $2$ в базисе, состоящем из всех булевых функций. Получена нижняя оценка сложности $\Omega(n^{3/2})$ для эффективно заданного $(n,n)$-оператора.
Библиогр. 8.

УДК: 519.714

Поступила в редакцию: 21.02.2005