Об оценках сложности схем из многовходовых функциональных элементов

В работе представлен метод получения нижних оценок сложности схем из функциональных элементов, основанный на замене рассматриваемого, быть может, достаточно сложного базиса, содержащего многовходовые элементы, на более простой базис, например, из двухвходовых элементов, с последующим использованием уже известных нижних оценок сложности схем в простом базисе. Эффективность предлагаемого метода демонстрируется на конкретных примерах нахождения асимптотики, и, в некоторых случаях, и точного значения для сложности реализации конкретных булевых функций – монотонных симметрических функций и функций с малым числом единиц.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 08–01–00863, и Программы Президента Российской Федерации поддержки ведущих научных школ, проект НШ 4470.2008.1.