Том 2, номер 4, 1995 г., Стр. 54-73

УДК 519.714
Е. А. Окольнишникова
О сравнении сложностей бинарных $k$-программ

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

Окольнишникова Е. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 3 мая 1995 г.