Cтраница 3
Разобьем множество переменных хг на bnl og n блоков по log п переменных в каждом. Функция, получаемая в действительности, зависит от значений, присвоенных переменным в b - 1 блоках. Пусть Bt - блок переменных, которым значения не присвоены. Если присваивание подходящих значений переменным не из Bt дает порядка 2 / п различных функций от переменных из В (, причем это выполняется для каждого г, l u log n, то любая древовидная схема для / должна содержать Vlog n логических элементов. [31]