Верещагин Н.К., Шень А. - Языки и исчисления, страница 8

. График функции ϕ(x) на отрезке[п. 3]Схемы из функциональных элементов35[0, 1] (рис. 4) показывает, что при итерациях функции ϕ дисбаланс(отклонение от середины) нарастает и последовательность стремится к краю отрезка. Надо только оценить число шагов.Рис. 4.

Итерируемая функция ϕ.Если вначале единицы составляют большинство из n аргументов(напомним, n нечётно), то их как минимум (n + 1)/2, так что p >(n + 1)/2n = 1/2 + 1/(2n). Таким образом, начальный дисбаланссоставляет как минимум 1/2n. А в конце нам нужно приблизитьсяк краю отрезка на расстояние 2−n .Итак, нам осталось доказать такую лемму (относящуюся скореек математическому анализу):Лемма. Пусть последовательность xk ∈ [0, 1] задана рекуррентнойформулой xk+1 = ϕ(xk ), гдеϕ(x) = 3x2 − 2x3 .Пусть x0 > 1/2 + 1/(2n).

Тогда последовательность xk монотонновозрастает и приближается к 1 на расстояние 2−n за O(log n) шагов.[Симметричное утверждение верно и при x0 6 1/2 − 1/(2n).]Идея доказательства: посмотрим на функцию вблизи точки 1/2 иу краёв отрезка. В точке 1/2 производная больше 1, поэтому удаление от 1/2 растёт как геометрическая прогрессия, и точка перейдёткакую-то фиксированную границу (например, 0,51) не позднее чемза O(log n) шагов. Затем потребуется O(1) шагов, чтобы дойти, скажем, до 0,99. В единице первая производная функции равна нулю,поэтому расстояние до единицы каждый раз примерно возводитсяв квадрат, и потому для достижения погрешности 2−n потребуется O(log n) шагов (как в методе Ньютона отыскания корня).

Всегополучается O(log n) + O(1) + O(log n) шагов, что и требовалось. 36Логика высказываний[гл. 1]На самом деле справедливо гораздо более сильное утверждение:существует схема размера O(n log n) и глубины O(log n), состоящаятолько из элементов И и ИЛИ, которая имеет n входов и n выходови осуществляет сортировку последовательности n нулей и единиц(это означает, что на выходе столько же единиц, сколько на входе,причём выходная последовательность всегда невозрастающая). Ясно, что средний бит выхода в такой ситуации реализует функциюбольшинства.При кажущейся простоте формулировки единственная известнаяконструкция такой схемы (сортирующая сеть AKS, придуманная Айтаи, Комлошом и Сцемереди в 1983 году) весьма сложна, и появлениекакой-то более простой конструкции было бы замечательным достижением.Многие нетривиальные результаты теории алгоритмов можно переформулировать в терминах сложности каких-то булевых функций.Например, есть вероятностный алгоритм проверки простоты большого числа (применяемый в системах шифрования для проверкипростоты чисел из нескольких тысяч цифр).

Используя этот алгоритм, можно доказать такой факт: существует схема проверки простоты n-битового числа (на вход подаются n цифр, на выходе появляется единица, если число простое, и нуль, если число составное),размер которой ограничен полиномом от n.Вернёмся к общим утверждениям о схемах и формулах. Мы ужеговорили, что с точки зрения измерения размера схемы и формулы —это разные вещи (схемы экономичнее, так как в них одинаковые подформулы учитываются только один раз). Оказывается, что размерформулы можно связать с глубиной схемы.Будем называть размером формулы число логических связок вней. Мы предполагаем, что формула использует конъюнкции, дизъюнкции и отрицания, и в схемах будем использовать такие же элементы.

Напомним, что размером схемы мы называли число элементов, а сложностью булевой функции — минимальный размер схемы,её вычисляющей. Сложность функции h обозначалась size(h) (точнееsizeB (h), где B — набор разрешённых функциональных элементов,но сейчас мы договорились использовать конъюнкции, дизъюнкциии отрицания и опускаем индекс B).Минимальный размер формулы, выражающей функцию h, будемобозначать fsize(h). Очевидно, size(h) 6 fsize(h). Более интересно,однако, следующее утверждение, связывающее размер схемы с глу-[п. 3]Схемы из функциональных элементов37биной формулы.

Обозначим через depth(h) минимальную глубинусхемы, вычисляющей функцию h.Теорема 16. Имеют место оценкиdepth(h)fsize(h) 6 c1иdepth(h) 6 c2 log fsize(h)(для некоторых констант c1 и c2 и для всех h). Другими словами,depth и log fsize отличаются не более чем в константу раз.

Первая оценка очевидна: если мы скопируем повторяющиесяфрагменты схемы, чтобы развернуть её в дерево, то глубина не изменится. Если она равна k, то в полученном дереве будет не больше2k − 1 элементов и соответствующая формула имеет размер не более 2k − 1. (Напомним, что элементами являются конъюнкции, дизъюнкции и отрицания, и потому ветвление не больше 2.)То же самое можно сказать индуктивно. Пусть глубина схемыравна k. Выход схемы является выходом некоторого элемента. Тогдана его входы подаются булевы функции глубины не больше k − 1.

Попредположению индукции их можно записать формулами размера2k−1 − 1. Таких формул максимум две, так что общий размер непревосходит 2(2k−1 − 1) + 1 = 2k − 1.Вторая оценка сложнее. Если мы будем преобразовывать формулу в схему естественным образом (введя вспомогательную переменную для каждой подформулы), то глубина получившейся схемыможет быть близка к размеру формулы, а не к его логарифму. Например, если формула имеет вид (. . .

((p1 ∧ p2 ) ∧ p3 ) ∧ . . . pn ), то у насполучится цепочка элементов И, у которых каждый следующий подвешен к левому входу предыдущего, и глубина равна n − 1. Конечно,если использовать ассоциативность конъюнкции, скобки можно переставить и получить более сбалансированное дерево глубины примерно log n, как и требуется. Но как выполнить такое преобразованиев случае произвольной формулы?Обозначим данную нам формулу через F . Выберем у неё некоторую подформулу G (как именно, мы объясним позже). Рассмотримформулу F0 , которая получится, если вместо G подставить 0 (ложь),а также формулу F1 , которая получится, если подставить 1.

Легкопонять, что F равносильна формуле ((F0 ∧¬G)∨(F1 ∧G)). Если теперьудастся заменить формулы F0 , F1 , G схемами глубины не больше k,то для F получится схема глубины не больше k + 3.Такое преобразование полезно, если все три формулы F1 , F0 , Gимеют заметно меньший размер, чем исходная формула F .38Логика высказываний[гл. 1]Лемма.

У любой формулы достаточно большого размера n естьподформула размера от n/4 до 3n/4.Доказательство. Каждая формула есть конъюнкция двух подформул, дизъюнкция двух подформул или отрицание подформулы.Начав со всей формулы, будем переходить к её подформулам, накаждом шаге выбирая из двух подформул наибольшую. Тогда накаждом шаге размер убывает не более чем в два раза, и потому мыне можем миновать промежуток [n/4, 3n/4], концы которого отличаются втрое.

(На самом деле тут есть небольшая неточность: размерформулы может убывать чуть быстрее, чем вдвое, так как размерформулы на единицу больше суммы размеров частей, но у нас естьзапас, поскольку концы промежутка отличаются втрое, а не вдвое.)Лемма доказана.Выбирая подформулу G с помощью этой леммы, мы гарантируем,что размер всех трёх формул F0 , F1 , G не превосходит 3/4 размераисходной формулы (подстановка нуля или единицы может толькоуменьшить размер формулы — некоторые части можно будет выбросить).Применим ко всем трём формулам F0 , F1 и G тот же приём,выделим в них подформулы среднего размера и так далее, пока мыне спустимся до формул малого размера, которые можно записать ввиде схем как угодно.

В итоге получится дерево с логарифмическимчислом уровней, на каждом из которых стоят схемы глубины 3, а влистьях находятся схемы глубины O(1).Другими словами, индукцией по длине формулы, выражающейфункцию h, мы доказываем, что depth(h) = O(log fsize(h)). 16. Определим глубину формулы как максимальное число вложенныхпар скобок; для единообразия будем окружать отрицание скобками и писать (¬A) вместо ¬A. Покажите, что при этом не получится ничего нового: минимальная глубина формулы, записывающей некоторую функциюf , совпадает с минимальной глубиной схемы, вычисляющей f .Определение формульной сложности fsize(h) зависит от выборабазиса. Оказывается, что здесь (в отличие от схемной сложности)выбор базиса может изменить fsize(h) более чем в константу раз.17.

Объясните, почему доказательство теоремы 7 не переносится наслучай формул.Так происходит с функцией p1 ⊕ p2 ⊕ . . . ⊕ pn (знак ⊕ обозначает сложение по модулю 2). Эта функция имеет формульную сложность O(n), если сложение по модулю 2 входит в базис. Однако вбазисе И, ИЛИ, НЕ она имеет большую сложность, как доказала[п. 3]Схемы из функциональных элементов39Б.