В работе оценивается сложность вычисления частичных булевых функций данного веса схемами из функциональных элементов в произвольном полном конечном базисе B, в котором каждой базисной функции φ_i приписан положительный вес ρ_i, а сложностью схемы называется сумма весов её элементов. Показано, что для любой частичной n-местной булевой функции f, определённой на области из D≥n элементов и равной единице на N наборах из этой области, при n→∞ справедливо неравенство L_B(f)≲ρ•(log₂(^D_N)/log₂log₂(^D_N))+O(n) где ρ - это минимум приведённых весов ρ_i/(r_i-1) базиса B, взятый по всем более чем одноместным элементам базиса.

частичная булева функция, вес функции, сложность схем

Математические вопросы и теория численных методов

Чашкин Александр Викторович,  ,  МГУ имени М.В. Ломоносова