Различные вопросы, связанные со сложностью вычисления булевых функций, изучаются давно и достаточно успешно [1], [2]. Одной из основных вычислительных моделей в этих исследованиях являются схемы из функциональных элементов. Важная особенность этой модели состоит в том, что каждая схема из функциональных элементов на любом наборе аргументов выполняет одно и то же число элементарных операций, т. е. при помощи схем изучается сложность функций в "худшем" случае. Однако не всегда число элементарных операций, выполненных в "худшем" случае, является реалистичной мерой сложности. Часто более важно знать среднее, по всем возможным аргументам, число операций, которое может значительно отличатся числа операций, выполненных в "худшем" случае. Для исследования средней сложности булевых функций используются неветвящиеся программы с условной остановкой. Эти программы обобщают понятие схемы из функциональных элементов и являются естественной моделью неветвящихся вычислений, т. е. вычислений в которых нет условного перехода и косвенной адресации, но есть возможность досрочного прекращения работы при выполнении определенного условия. Такие вычисления можно представить следующим образом. Вычисления выполняет процессор, снабженный памятью, состоящей из отдельных ячеек. Процессор способен вычислять некоторое количество двухместных элементарных функций; множество этих функций назовем базисом вычисления. Каждая ячейка памяти в любой момент времени доступна процессору как для чтения, так и для записи информации. Процессор работает под управлением программы, являющейся последовательностью элементарных операторов двух видов. Каждый оператор первого вида вычисляется значение некоторой базисной функции, аргументами которой является содержимое определенных ячеек памяти. Вычисленный результат также помещается в одну из ячеек памяти. Оператор второго вида может прекратить выполнение программы. Каждый такой оператор имеет единственный аргумент - содержимое некоторой ячейки памяти. Если значение аргумента равно единице, то процессор прекращает работу. Если значение аргумента равно нулю, то выполняется следующий оператор программы. В памяти выделяется множество особых ячеек содержимое которых после прекращения работы объявляется результатом работы программы. Естественной мерой сложности таких программ является среднее по всем возможным аргументам время работы.

При изучении средней сложности естественным образом возникает вопрос о ее связи со сложностью в худшем случае - схемной сложностью. В частности интересен вопрос о том, насколько сильно могут различаться эти две меры сложности для конкретной булевой функции. Ниже показано, что эффекты, связанные с возможностью досрочного прекращения вычислений, начинают проявляться уже при вычислении булевых функций трех переменных. Известно, что существуют функции трех переменных схемная сложность которых равна четырем. В то же время средняя сложность любой булевой функции трех переменных не превосходит 2.5. С ростом числа переменных средняя сложность может отличаться от схемной сложности значительно сильнее. В [3] рассмотрена средняя сложность дизъюнкции, конъюнкции и линейной функции растущего числа аргументов. Для дизъюнкции и конъюнкции установлены асимптотически точные формулы средней сложности, оказавшиеся константами 8/3 и 11/3 соответственно. Следовательно, для дизъюнкции и конъюнкции отношения схемной и средней сложностей по порядку величины совпадают с числом их аргументов. Средняя сложность линейной функции равна ее сложности в худшем случае, т. е. досрочное прекращение вычислений не позволяет упростить вычисление линейной функции. В [4] показано, что существуют булевы функции n переменных для которых схемная сложность больше их средней сложности по порядку величины в (2ⁿ/n)^1/2 раз, причем функций, для которых это отношение по порядку величины больше, не существует. При растущем числе аргументов средняя сложность "почти всех" булевых функций и булевых (m, n)-операторов - систем, состоящих из m булевых функций n переменных, отличается от их схемной сложности только в постоянное число раз. В частности справедлива следующая теорема.

Теорема 1. Пусть n неограниченно возрастает, m=n^O(1). Тогда:
(i) для почти каждого булевого (n,m)-оператора f

Теорема 2. Пусть n неограниченно возрастает. Тогда:
(i) для почти каждой монотонной булевой функции f от n переменных

(ii) для каждой монотонной булевой функции f от n переменных

где a и b - некоторые положительные константы.

Из теоремы 2 следует, что средняя сложность почти каждой монотонной функции от n переменных меньше ее схемной сложности по порядку в n^1/2 раз [6].

Ряд других результатов, касающихся взаимосвязи средней и схемной сложностей булевых функций, можно найти в [4] и [5]. Сравнение результатов [3], [4], теоремы 1 и теоремы 2 ставит ряд интересных вопросов. Например, насколько сложной может быть булева функция (булев оператор) средняя сложность которой не меньше (асимптотически не меньше) ее схемной сложности?

ЛИТЕРАТУРА

[1] Лупанов О.Б. Об одном подходе к синтезу управляющих систем - принципе локального кодирования // Проблемы кибернетики. М.: Наука, 1965. Вып. 14, 31-110.

[2] Шоломов Л.А. О реализации недоопределенных булевых функций схемами из функциональных элементов // Проблемы кибернетики. М.: Наука, 1969. Вып. 21, 215-226.

[3] Чашкин А.В. Среднее время вычисления значений элементарных булевых функций.

[4] Чашкин А.В. О среднем времени вычисления значений булевых функций // Дискретный анализ и исследование операций. 1997, N1, 60-78.

[5] Чашкин А.В. О вычислении булевых функций вероятностными программами // Дискретный анализ и исследование операций. 1997, N3, 49-68.

[6] Забалуев Р.Н. О средней сложности вычислений монотонных функций. // Материалы XV международной школы-семинара "Синтез и сложность управляющих систем". Новосибирск, 2004, 40-45.

---