О сложности реализации формулами степеней булевых функций

Рассматриваются операция бесповторного произведения булевых функций и порожденная ею операция возведения булевой функции в степень. Степени булевой функции были рассмотрены Б. А. Субботовской (впервые в 1963 г.) и автором при решении задачи сравнения булевых базисов. В настоящей статье дан критерий, позволяющий установить, реализуется ли последовательность степеней функции $f$ формулами в базисе Б с линейной или нелинейной сложностью. Библиогр. 8.