Функции трех переменных
Эффекты, связанные с возможностью досрочного прекращения вычислений, начинают проявляется уже при вычислении булевых функций трех переменных. Нетрудно показать, что схемная сложность каждой булевой функции трех переменных не превосходит четырех, причем существуют функции, например функция голосования g, сложность которых равна четырем. Покажем, что средняя сложность любой булевой функции трех переменных не превосходит 2.5.
Пусть f - произвольная булева функция трех переменных. Разложим f по первой переменной
Легко видеть, что программа P
|
|
p1: z = f1(x2, x3) |
|
|
|
p2: Stop(x1) |
|
|
|
p3: z = f2(x2, x3) |
|
вычисляет функцию f. Действительно, в соответствии с определением функции, вычисляемой еветвящейся программой с условной остановкой, для P(x) справедливы равенства
На четырех наборах - (1,0,0), (1,0,1), (1,1,0), (1,1,1) - программа P выполняет два действия, на остальных четырех наборах - три. Поэтому
Теперь покажем, что средняя сложность функции голосования
не меньше, чем 2.5. Пусть P
- программа, вычисляющая g с минимальным средним временем. Если первый оператор остановки s1 является третьим оператором P, то очевидно, что T(P) не меньше трех. Так как в любой программе на первом месте должен стоять функциональный оператор, то далее полагаем, что s1 является вторым оператором P. Теперь для доказательства нижней оценки достаточно показать, что в P, оператор остановки прекращает вычисления не более чем на четырех наборах из восьми, так как в этом случае средняя сложность будет не меньше 2.5.
Легко видеть, что нулевым аргументом оператора остановки может быть либо выходная, либо независимая переменная, т. е. начало программы P имеет следующий вид:
|
p1: z = f(x1, x2) |
z = f(x1, x2) |
|
p2: Stop(z) |
Stop(xi) |
В первом случае если TP(x) = 2, то P(x) = 1.
Так как функция голосования равна единице ровно на четырех наборах из восьми, то оператор p2 прекращает вычисления не более чем на четырех наборах.
Во втором случае очевидно, что p2 прекращает вычисления ровно на четырех наборах.
