О сложности вычисления пары одночленов от двух переменных

Изучается обобщение задачи об эффективном вычислении степени $x^n$ по заданным $x$ и $n$ (или эквивалентной ей задачи о минимальной аддитивной цепочке для числа $n$), где $n\in\mathbf N$. Сложность вычисления системы одночленов $\{x^ay^b,x^cy^d\}$, то есть минимальное число операций умножения, достаточное для вычисления (допускается многократное использование промежуточных результатов) по переменным $x$ и $y$, а также заданным показателям $a$, $b$, $c$ и $d$ системы одночленов $\{x^ay^b,x^cy^d\}$, обозначим через $l(x^ay^b,x^cy^d)$. В работе доказано, что при выполнении условия $\max\{a,b,c,d\}\to\infty$, справедливо соотношение
$$ l(x^{a}y^{b},x^{c}y^{d})\sim\log_2(|ad-bc|+a+b+c+d). $$

Работа выполнена при поддержке Российского фонда фундаментальный исследований, проект 05-01-00994, программой Президента Российской Федерации поддержки ведущих научных школ, проект НШ–1807.2003.1, и программой Университеты России, проект УР.04.02.528.