О сложности булевых функций с малым числом единиц

Рассматривается класс булевых функций $F_{n,k}$, состоящий из всех тех функций от $n$ переменных, каждая из которых обращается в единицу ровно на $k$ наборах значений переменных. Для функций из $F_{n,k}$ получены линейные по $n$ оценки сложности реализации схемами из функциональных элементов над базисом, содержащим все булевы функции от двух переменных, кроме двух линейных функций, $x\oplus y$ и $x\oplus y\oplus1$. Из этих оценок следует, что при небольших значениях $k$, например, при $k<\ln n$, известный метод Финикова позволяет строить асимптотически минимальные схемы для всех функций из $F_{n,k}$. В некоторых случаях полученные нижние оценки сложности схем позволяют доказывать минимальность рассматриваемых схем.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 02–01–00985, грантом НШ-1807.2003.1 программы Президента Российской Федерации поддержки ведущих научных школ и программой «Университеты России».