О сравнении сложностей бинарных $k$-программ

Сравниваются сложности реализации булевых функций бинарными $k$-npoграммами при различных значениях $k$. Показано, что для любого натурального $k,k\ge 2$, существуют натуральное $s_k$ (не превосходящее $k^2$) и последовательность булевых функций такие, что сложность реализации каждой функции из этой последовательности в классе бинарных $k$-программ в экспоненциальное число раз (по числу переменных булевой функции) превосходит сложность реализации той же функции в классе бинарных $s_k$-программ.
Ил. 2, табл. 1, библиогр. 13