О сложности вычисления экспоненты

Рассматривается вычисление арифметической функции $x^y$ в коде $C$, в котором длины двоичных записей $x^y$, $x\mathbin{\dot{\smash{-}}}y$, $[x/y]$ существенно меньше $2^n$, где $n$ – длина двоичной записи $x$, $y$. Доказывается, что при этих условиях сложность вычисления хотя бы одной из функций $x^y$, $x\mathbin{\dot{\smash{-}}}y$, $[x/y]$ в $C$-коде или сложность декодирования становится не элементарной по Кальмару. Аналогичные результаты получены для сложности вычислений схемами из функциональных элементов. Библ. 4 назв.