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

также [9] и [33].)Теорема 8, однако, ничего не говорит о сложности конкретных булевых функций. Ситуация здесь такова. Есть разнообразные методыи приёмы получения верхних оценок. Но про нижние оценки неизвестно практически ничего. Про многие функции мы подозреваем,что их сложность велика (экспоненциально зависит от числа входов),но доказать это пока не удаётся.

Весьма нетривиальные идеи позволяют доказывать экспоненциальные нижние оценки для некоторыхспециальных классов схем, например, схем из монотонных элементовили схем ограниченной глубины (использующих элементы И и ИЛИс произвольным числом входов). Получение экспоненциальных оценок для более общих схем — один из возможных подходов к знаменитой проблеме перебора, центральной проблеме теории сложностивычислений.Мы не будем углубляться в эту теорию, а приведём лишь несколько верхних оценок для конкретных задач. При этом мы не претендуем на полноту, а хотим лишь показать несколько интересных идейи приёмов.Рассмотрим функцию сравнения двух n-битовых чисел. Она имеет 2n аргументов (n для одного числа и n для другого); её значениеравно 1, если первое число больше второго, и 0 в противном случае.[п.

3]Схемы из функциональных элементов27Обозначим эту функцию Compn .Теорема 9. Пусть B — полный набор функций. Существует такаяконстанта C, что sizeB (Compn ) 6 Cn. Заметим, что поскольку в формулировке теоремы оценка размера проводится с точностью до константы, то выбор конкретногобазиса не имеет значения. Другими словами, мы можем предполагать, что любое конечное число необходимых нам функций в этомбазисе есть.Схема сравнения чисел будет рекурсивной (чтобы сравнить двачисла, мы отдельно сравниваем их левые и правые половины, а затемобъединяем результаты). При этом, как часто бывает, надо усилитьутверждение, чтобы индукция прошла.

А именно, мы будем строитьсхему с 2n входами x1 , . . . , xn , y1 , . . . , yn и двумя выходами, котораяуказывает, какой из трёх случаев x < y, x = y или x > y имеет место.(Здесь x, y — числа, записываемое в двоичной системе как x1 . . . xnи y1 , . . . , yn .) Два выходных бита кодируют четыре возможности, анужно только три, так что есть некоторый запас. Для определённости можно считать, что первый выходной бит истинен, если числаравны, а второй — если x < y.

Тогда возможны три варианта сигналов на выходе: 10 (равенство), 01 (при x < y) и 00 (при x > y).Объясним теперь, как собрать, скажем, схему сравнения двух16-разрядных чисел. Соберём отдельно схему сравнения старших8 разрядов и младших 8 разрядов. Каждая из них даст ответ в форме двух битов. Теперь из этих четырёх битов надо собрать два.

(Еслив старших разрядах неравенство, то оно определяет результат сравнения; если старшие разряды равны, то результат сравнения определяется младшими разрядами.) Написанная в скобках фраза определяет булеву функцию с четырьмя битами на входе и двумя битами на выходе, и может быть реализована некоторой схемой фиксированного размера.

Таким образом, если через T (n) обозначитьразмер схемы, сравнивающей n-битовые числа, то получаем оценкуT (2n) 6 2T (n)+c, где c — некоторая константа, зависящая от выборабазиса. Отсюда следует, что T (2k ) 6 c0 2k при некотором c0 . В самомделе, для достаточно большого c0 можно доказать по индукции, чтоT (2k ) 6 c0 2k − c (мы должны усилить неравенство, вычтя из правойчасти c, чтобы индуктивный шаг прошёл; база индукции остаетсяверной, если c0 достаточно велико).Ту же самую оценку можно объяснить и наглядно.

Наша схема имеет вид иерархического дерева. На каждом уровне из двухдвухбитовых сигналов получается один. Остаётся вспомнить, что в28Логика высказываний[гл. 1]полном двоичном дереве число внутренних вершин (которое определяет размер схемы) на единицу меньше числа листьев. (В турнире поолимпийской системе число игр на единицу меньше числа команд,так как после каждой игры одна команда выбывает.)Все внутренние вершины и все листья (где сравниваются два бита) представляют собой схемы ограниченного размера, откуда и вытекает оценка T (2k ) 6 c0 2k .Осталось лишь сказать, что делать, если размер чисел (которыймы обозначали через n) не есть точная степень двойки. В этом случаеможно увеличить размер до ближайшей сверху степени двойки (неболее чем в два раза) и подать на старшие разряды входов нули.Оба действия приводят к увеличению размера схемы не более чем вконстанту раз. Перейдём к сложению двух n-разрядных чисел.

(Строго говоря,тут возникает не булева функция, а функция Bn × Bn → Bn+1 , новсе наши определения очевидно переносятся на этот случай.)Теорема 10. Существует схема размера O(n), осуществляющаясложение двух n-битовых чисел. Напомним смысл обозначения O(n): нам надо построить схему сложения n-битовых чисел, имеющую размер не более Cn длянекоторого C и для всех n.Вспомним, как складывают числа в столбик:0111001101110100Верхняя строка — биты переноса, нижняя — результат. Заметим,что каждый из битов переноса или результата определяется тремядругими битами (бит результата равен сумме двух битов слагаемыхи бита переноса по модулю 2, а бит переноса равен 1, если хотя быдва из этих трёх битов равны 1).

Поэтому можно составить схему,которая вычисляет эти биты справа налево и имеет размер O(n). Заметим, что теорему 9 легко вывести из теоремы 10: чтобы сравнить числа x и y, сложим число (2n − 1) − x (то есть число x, в котором все единицы заменены нулями и наоборот) и число y. Если встаршем разряде появится единица, то y > x, а если нет, то y 6 x.Остаётся заметить, что и сложение, и обращение битов в числе xтребуют схем линейного размера. Таким образом, сравнение чиселсводится к вычислению бита переноса. Верно и обратное: вычисление[п.

3]Схемы из функциональных элементов29бита переноса сводится к сравнению двух чисел (обратим в одном изслагаемых все биты).Тем не менее конструкция, использованная при доказательстветеоремы 9, имеет некоторые преимущества. Назовём глубиной схемы максимальное число элементов на пути от входа к выходу.

Еслипредставить себе, что сигнал на выходе элемента появляется не сразу после подачи сигналов на входы, а с некоторой задержкой, тоглубина схемы определяет суммарную задержку. Легко понять, чторекурсивная схема сравнения имела глубину O(log n) (число уровней пропорционально логарифму размера входа), в то время какпостроенная только что схема сложения имеет глубину, пропорциональную n (биты переноса вычисляются последовательно, справаналево). Но можно соединить эти два результата:Теорема 11. Существует схема сложения двух n-битовых чиселразмера O(n) и глубины O(log n). Как мы видели, проблема в том, что биты переноса вычисляются последовательно, а не параллельно. Если удастся их все вычислить схемой размера O(n) и глубины O(log n), дальнейшее очевидно.Вычисление битов переноса равносильно сравнению, так что длядоказательства теоремы достаточно научиться сравнивать параллельно все «суффиксы» двух n-битовых чисел x1 .

. . xn и y1 . . . yn ,т. е. для каждого i сравнить числа xi xi+1 . . . xn и yi yi+1 . . . yn .Вспомним, что мы делали при сравнении чисел (скажем, длины 8). На нижнем уровне мы сравнивали биты:x1y1x2y2x3y3x4y4x5y5x6y6x7y7x8y8На следующем уровне мы сравнивали двузначные числаx1 x2y1 y2x3 x4y 3 y4x5 x6y5 y6x7 x8y7 y8затем четырёхзначныеx1 x2 x3 x4y1 y2 y 3 y4x5 x6 x7 x8y5 y6 y 7 y 8и, наконец, восьмизначные:x1 x2 x3 x4 x5 x6 x7 x8y 1 y 2 y3 y4 y 5 y 6 y7 y 830Логика высказываний[гл.

1]Таким образом, для суффиксов длины 8, 4, 2 и 1 результаты сравнения уже есть. Для суффикса длины 6 результат можно получить,комбинируя результат сравнения x3 x4 ?y3 y4 и x5 x6 x7 x8 ?y5 y6 y7 y8 . После этого у нас есть информация о суффиксах всех чётных длин, исоединяя её с информацией с первого этапа, получаем сведения провсе суффиксы. Например, для сравнения суффиксов длины 7, тоесть x2 . . .

x8 и y2 . . . y8 , мы соединяем результаты сравнения x2 иy2 с результатами сравнения суффиксов длины 6, то есть x3 . . . x8 иy3 . . . y 8 .В общем случае картина такая: после «сужающегося дерева» мыстроим «расширяющееся»; за k шагов до конца мы знаем результатысравнения всех суффиксов, длины которых кратны 2k . Это деревоимеет размер O(n) и глубину O(log n), что завершает доказательство. 14. Покажите, что вычитание двух n-битовых чисел по модулю 2n выполняется схемой размера O(n) и глубины O(log n). (Указание: вычитаниелегко сводится к сложению, если заменить нули на единицы и наоборот.)Теперь займёмся умножением. Схема умножения двух n-разрядных чисел имеет 2n входов (по n для каждого множителя) и 2nвыходов для произведения.Посмотрим, какие оценки даёт обычный способ умножения чиселстолбиком.

В нём умножение двух n-разрядных чисел сводится ксложению n копий первого числа (частично заменённых на нули взависимости от цифр второго числа) со сдвигами.Получение этих копий требует схемы размера O(n2 ) (общее число цифр в копиях) и глубины O(1). Сложение двух 2n-разрядныхчисел мы можем выполнить с помощью схемы размера O(n) и глубины O(log n), так что необходимые n−1 сложений можно выполнитьсхемой размера O(n2 ) и глубины O(log2 n) (если складывать сначалапопарно, потом результаты снова попарно и т. д.).

Оказывается, этотрезультат можно улучшить. Наиболее экономные способы основанына преобразовании Фурье (о них можно прочесть в книге [1]). С ихпомощью, например, можно построить схему умножения n-битовыхчисел, имеющую размер n logc n.Эти методы далеко выходят за рамки нашего обсуждения, но дваулучшения мы приведём.Теорема 12.