№2 11 Заметим, что доказательство этой оценки, по существу, совпадает с доказательством оценки сложности реализации линейной булевой функции x1 ⊕.⊕xn формулами в базисе {&,∨,¬} или последовательнопараллельными контактными схемами (см. <...> ). В [5] для последней задачи доказана нижняя оценка базиса {x + y, 1}∪ {ax : a ∈ R}, состоящего из произвольного нелинейного многочлена и множества линейных функций (доказано, что в этом базисе выразим любой многочлен). <...> Аналогичную задачу можно рассматривать и для произвольного базиса Bk = {x+y,xk}∪ {ax : a ∈ R}. <...> Можно изучать подобные задачи и для произведения x1 . xn формулами в базисе B = {x+y,x2}∪{ax : a ∈ R}. <...> Для случая реализации схемами это неверно, так как очевидно, что LB(n)= O(n). <...> B = {x + y,x2}∪ {ax : a ∈ R} и возникла задача о наименьшем числе линейных форм li, таких, что некоторая линейная комбинация их n-х степеней будет равна x1 . xn. <...> Представление в виде суммыстеПри попытке решить задачу о сложности вычисления произведения x1 . xn формулами в базисе пеней линейных форм в современной терминологии есть реализация схемами (формулами) глубины два вбазисе B. <...> Первый автор относился к задаче о представлении произведения суммами степеней как к олимпиадной и предлагал ее частные случаи на студенческие и школьные олимпиады, но в общем виде доказывать нижнюю оценку не умел. <...> Для олимпиад задача показалась слишком сложной, а смысла в публикации тогда никто из авторов не усмотрел. <...> Недавно первому автору стало известно, что в [6] рассматривалась эта (и чуть более общая) задача и было доказано, в частности, что число слагаемых в любом тождестве x1 . xn = ld 1 +.+ld s , где li — аффинные формы, не меньше 2n/(d+1), а в [7] доказано, что число слагаемых в любом тождестве x1 . xn = Qe1 1 +. <...> +Qess , где Qi — многочленыстепени не выше d, удовлетворяет неравенству ln s =Ω(n/2d)+O(d ln n), в частности при d =1получается нижняя оценка s 2Ω(n). <...> В [6 <...>