Том 8, серия 1, номер 4, 2001 г., Стр. 103-111

УДК 519.714
Д. Ю. Черухин
О сложности реализации формулами степеней булевых функций

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

Черухин Д. Ю. ¹
1. MГУ, мех.-мат. факультет,
Воробьевы горы, 119899 Москва, Россия
е-mail: dyucher@mech.math.msu.su

Статья поступила 25 июля 2001 г.