Схемы из функциональных элементов
Формулы представляют собой способ записи композиции функций. Например, если мы сначала применяем функцию, а потом функцию, это можно записать формулой . Но есть и другой способ: можно изобразить каждую функцию в виде прямоугольника с "входом"и "выходом"и соединить выход функции со входом функции (рис. 2.1).
Рис. 2.1. Два способа изобразить композицию g°f
Такое представление отнюдь не является чисто теоретическим. В течении нескольких десятков лет электронная промышленность выпускает микросхемы, которые выполняют логические операции. Такая микросхема имеет электрические контакты, напряжение на которых кодирует логические значения И и Л. Конкретное напряжение зависит от типа схемы, но обычно это несколько вольт, и высокий потенциал (относительно заземления) считается единицей, а низкий нулем.
Одной из типичных схем является схема И-НЕ, она имеет два входа и один выход. Сигнал на выходе является отрицанием конъюнкции сигналов на входе. Другими словами, на выходе появляется высокий потенциал (сигнал ) тогда и только тогда, когда на одном из входов потенциал низкий (). Из такой схемы легко получить схему НЕ (изменяющую уровень сигнала на противоположный), соединив проводом два входа. При этом на оба входа поступает один и тот же сигнал, и операция И его не меняет (), а НЕ меняет на противоположный. Взяв два элемента И-НЕ и используя второй из них в качестве элемента НЕ, инвертирующего сигнал с выхода первого элемента, получаем схему, которая реализует функцию И. А если поставить два элемента НЕ перед каждым из входов элемента И-НЕ, получим схему, реализующую функцию ИЛИ: .
Теорема 3 о полноте системы связок теперь гарантирует, что любую булеву функцию можно реализовать в виде схемы. Надо иметь в виду, однако, что предлагаемая в ее доказательстве конструкция (дизъюнктивная нормальная форма) имеет скорее теоретический интерес, поскольку приводит к схемам очень большого размера даже для простых функций (если число аргументов велико). Например, схема, сравнивающая два -битных числа, должна иметь входа и поэтому в ее реализации с помощью дизъюнктивной нормальной формы будет порядка
элементов — что мало реально. (Между тем такую схему можно построить гораздо проще, из нескольких сотен элементов.)
Поэтому вопрос о том, сколько элементов нужно для реализации той или иной функции, представляет большой интерес — как практический, так и философский. (Одна из центральных проблем математики и информатики, так называемая "проблема перебора", может быть сформулирована в этих терминах.)
Мы сейчас дадим более формальное определение схемы и реализуемой ей булевой функции. Но прежде всего ответим на такой вопрос — почему мы вообще говорим о схемах? Ведь можно записать композицию булевых функций в виде формулы, не будет ли это то же самое?
Оказывается, не совсем, и разницу легко увидеть на примере (рис. 2.2).
Рис. 2.2. Элемент входит в формулу дважды
Здесь один и тот же элемент схемы () приходится указывать в формуле дважды, поскольку его выход используется в качестве входа двух других элементов. Схемы, в которых такого ветвления нет (на практике ветвление вполне возможно, хотя и ограничено "нагрузочной способностью выхода", как говорят инженеры), как раз и соответствуют формулам. Но в общем случае полученная из данной схемы формула может быть длинной, даже если схема содержит небольшое число элементов, поскольку число копий может расти экспоненциально с ростом глубины схемы.
Хотя идея образования схемы из функциональных элементов, реализующих булевы функции, достаточно наглядна, дадим более формальное определение. Фиксируем некоторый набор булевых функций . Пусть имеется булевых (принимающих значения
и ) переменных , называемых входами. Пусть также имеется некоторое число булевых переменных , называемых проводниками. Пусть для каждого проводника схемы задана булева функция из , выражающая его значение через другие проводники и входы. При этом требуется, чтобы не было циклов (цикл образуется, когда зависит от , которое зависит от , которое зависит от ). Пусть, кроме того, среди проводников выделен один, называемый выходом. В таком случае говорят, что задана схема из функциональных элементов в базисе
с входами. Число называют размером схемы. (С точки зрения инженера размер — это число использованных элементов, а базис — это ассортимент доступных ему элементов.)
Отсутствие циклов гарантирует, что есть проводник, зависящий только от входов (иначе можно было бы найти цикл: возьмем какой-то проводник, затем возьмем тот проводник, от которого он зависит и т. д.). Значение этого проводника, таким образом, однозначно определяется сигналами на входах. Среди оставшихся проводников также нет цикла, поэтому можно найти один из них, зависящий только от уже известных, и определить его значение. Перенумеровав проводники в таком порядке, мы можем записать последовательность присваиваний
в правых частях которых стоят функции из , примененные ко входам и уже найденным значениям. При этом можно считать, что результат схемы есть
(все последующие присваивания уже не нужны). Такая программа определяет при известных значениях входов, и тем самым вычисляет некоторую булеву функцию.
Теперь набор булевых функций можно назвать полным, если любая булева функция может быть задана схемой из -элементов (существует программа, ее вычисляющая, при этом в правых частях присваиваний стоят функции из). Ясно, что это определение полноты равносильно прежнему, то есть возможности записать булеву функцию в виде формулы со связками из (как мы говорили, разница только в том, что один и тот же элемент будет фигурировать в формуле многократно).
Сложностью булевой функции относительно называют минимальный размер схемы из - элементов, вычисляющей функцию. Его обозначают.
Теорема 7. Пусть и — два полных набора булевых функций. Тогда соответствующие меры сложности отличаются не более чем на постоянный множитель: найдется такое число , что и
для любой функции.
Утверждение почти очевидно: поскольку наборы и полны, то каждая функция одного из наборов может быть вычислена какой-то схемой, составленной из элементов другого набора. Теперь можно взять в качестве наибольший размер таких схем, и неравенства будут выполняться: каждую строку программы можно заменить на (или меньше) строк с использованием функций другого набора.
Что можно сказать о сложности произвольной булевой функции
аргументов? Следующая теорема показывает, что она экспоненциально зависит от (для "наугад взятой"функции).
Теорема 8.(а) Пусть . Тогда сложность любой булевой функции аргументов не превосходит для всех достаточно больших. (б) Пусть. Тогда сложность большинства булевых функций аргументов не меньше для всех достаточно больших.
Прежде всего заметим, что по предыдущей теореме не имеет значения, какой полный базис выбрать (изменение значения более существенно, чем умножение сложности на константу).
Первое утверждение теоремы очевидно: размер схемы, реализующей дизъюнктивную нормальную форму с переменными, есть , поскольку имеется не более конъюнктов размера . (Напомним смысл -обозначений: означает, что существует верхняя оценка вида для некоторой константы .) Осталось заметить, что при достаточно больших (напомним, что).
Чтобы доказать второе утверждение, оценим число различных схем (скажем, в базисе И, ИЛИ, НЕ) размера с аргументами. Каждая такая схема может быть описана последовательностью из присваиваний, выражающих одну из переменных через предыдущие. Для каждого присваивания есть не более вариантов (три типа операций — конъюнкция, дизъюнкция, отрицание, и каждый из не более чем двух аргументов выбирается среди не более чем вариантов). Отсюда легко получить оценку на число всех функций сложности не более (считая ).
Всего булевых функций с аргументами имеется . Из сравнения этих формул видно, что что при и при достаточно больших булевы функции сложности меньше
составляют меньшинство, так как
много меньше .
12. Проведите вторую часть рассуждения более подробно и покажите, что при некотором сложность большинства булевых функций с аргументами не меньше .
Верхнюю оценку в теореме 8 можно усилить и показать, что сложность любой булевой функции аргументов не превосходит.
13. (a) Покажите, что можно построить схему размера с выходами, реализующую все возможных конъюнктов длины (для каждого— свой выход). (Указание: такую схему можно построить индуктивно.) (б) Покажите, что можно построить схему размера с выходами, реализующую все булевых функций аргументов. (Указание: эту схему также можно построить индуктивно.) (в) Пусть — булева функция, аргументы которой разбиты на две группы. Покажите, что ее можно записать в виде дизъюнкции членов, каждый из которых имеет вид , где — конъюнкт, а — произвольная булева функция. Вывести отсюда упомянутую выше оценку . (Указание: разумно положить , . См. также [9] и [33].)
Теорема 8, однако, ничего не говорит о сложности конкретных булевых функций. Ситуация здесь такова. Есть разнообразные методы и приемы получения верхних оценок. Но про нижние оценки неизвестно практически ничего. Про многие функции мы подозреваем, что их сложность велика (экспоненциально зависит от числа входов), но доказать это пока не удается. Весьма нетривиальные идеи позволяют доказывать экспоненциальные нижние оценки для некоторых специальных классов схем, например, схем из монотонных элементов или схем ограниченной глубины (использующих элементы И и ИЛИ с произвольным числом входов). Получение экспоненциальных оценок для более общих схем — один из возможных подходов к знаменитой проблеме перебора, центральной проблеме теории сложности вычислений.
Мы не будем углубляться в эту теорию, а приведем лишь несколько верхних оценок для конкретных задач. При этом мы не претендуем на полноту, а хотим лишь показать несколько интересных идей и приемов.
Рассмотрим функцию сравнения двух -битовых чисел. Она имеет аргументов ( для одного числа и для другого); ее значение равно , если первое число больше второго, и в противном случае.
Обозначим эту функцию.
Теорема 9. Пусть — полный набор функций. Существует такая константа , что .
Заметим, что поскольку в формулировке теоремы оценка размера проводится с точностью до константы, то выбор конкретного базиса не имеет значения. Другими словами, мы можем предполагать, что любое конечное число необходимых нам функций в этом базисе есть.
Схема сравнения чисел будет рекурсивной (чтобы сравнить два числа, мы отдельно сравниваем их левые и правые половины, а затем объединяем результаты). При этом, как часто бывает, надо усилить утверждение, чтобы индукция прошла. А именно, мы будем строить схему с входами и двумя выходами, которая указывает, какой из трех случаев , или имеет место. (Здесь — числа, записываемое в двоичной системе как и .) Два выходных бита кодируют четыре возможности, а нужно только три, так что есть некоторый запас. Для определенности можно считать, что первый выходной бит истинен, если числа равны, а второй — если . Тогда возможны три варианта сигналов на выходе: (равенство),
(при ) и (при .
Объясним теперь, как собрать, скажем, схему сравнения двух -разрядных чисел. Соберем отдельно схему сравнения старших разрядов и младших разрядов. Каждая из них даст ответ в форме двух битов. Теперь из этих четырех битов надо собрать два. (Если в старших разрядах неравенство, то оно определяет результат сравнения; если старшие разряды равны, то результат сравнения определяется младшими разрядами.) Написанная в скобках фраза определяет булеву функцию с четырьмя битами на входе и двумя битами на выходе, и может быть реализована некоторой схемой фиксированного размера. Таким образом, если через обозначить размер схемы, сравнивающей -битовые числа, то получаем оценку
где — некоторая константа, зависящая от выбора базиса. Отсюда следует, что
при некотором. Всамом деле, для достаточно большого можно доказать по индукции, что
(мы должны усилить неравенство, вычтя из правой части , чтобы индуктивный шаг прошел; база индукции остается верной, если достаточно велико).
Ту же самую оценку можно объяснить и наглядно. Наша схема имеет вид иерархического дерева. На каждом уровне из двух двухбитовых сигналов получается один. Остается вспомнить, что в полном двоичном дереве число внутренних вершин (которое определяет размер схемы) на единицу меньше числа листьев. (В турнире по олимпийской системе число игр на единицу меньше числа команд, так как после каждой игры одна команда выбывает.)
Все внутренние вершины и все листья (где сравниваются два бита) представляют собой схемы ограниченного размера, откуда и вытекает оценка .
Осталось лишь сказать, что делать, если размер чисел (который мы обозначали через) не есть точная степень двойки. В этом случае можно увеличить размер до ближайшей сверху степени двойки (не более чем в два раза) и подать на старшие разряды входов нули. Оба действия приводят к увеличению размера схемы не более чем в константу раз.
Перейдем к сложению двух -разрядных чисел. (Строго говоря, тут возникает не булева функция, а функция , но все наши определения очевидно переносятся на этот случай.)
Теорема 10. Существует схема размера , осуществляющая сложение двух -битовых чисел.
Напомним смысл обозначения : нам надо построить схему сложения -битовых чисел, имеющую размер не более для некоторого и для всех.
Вспомним, как складывают числа в столбик:
Верхняя строка — биты переноса, нижняя — результат. Заметим, что каждый из битов переноса или результата определяется тремя другими битами (бит результата равен сумме двух битов слагаемых и бита переноса по модулю, а бит переноса равен , если хотя бы два из этих трех битов равны). Поэтому можно составить схему, которая вычисляет эти биты справа налево и имеет размер .
Заметим, что теорему 9 легко вывести из теоремы 10: чтобы сравнить числа и , сложим число (то есть число , в котором все единицы заменены нулями и наоборот) и число. Если в старшем разряде появится единица, то , а если нет, то . Остается заметить, что и сложение, и обращение битов в числе
требуют схем линейного размера. Таким образом, сравнение чисел сводится к вычислению бита переноса. Верно и обратное: вычисление бита переноса сводится к сравнению двух чисел (обратим в одном из слагаемых все биты).
Тем не менее конструкция, использованная при доказательстве теоремы 9, имеет некоторые преимущества. Назовем глубиной схемы максимальное число элементов на пути от входа к выходу. Если представить себе, что сигнал на выходе элемента появляется не сразу после подачи сигналов на входы, а с некоторой задержкой, то глубина схемы определяет суммарную задержку. Легко понять, что рекурсивная схема сравнения имела глубину (число уровней пропорционально логарифму размера входа), в то время как построенная только что схема сложения имеет глубину, пропорциональную (биты переноса вычисляются последовательно, справа налево). Но можно соединить эти два результата:
Теорема 11. Существует схема сложения двух -битовых чисел размера и глубины .
Как мы видели, проблема в том, что биты переноса вычисляются последовательно, а не параллельно. Если удастся их все вычислить схемой размера и глубины , то дальнейшее очевидно.
Как мы упоминали, вычисление битов переноса равносильно сравнению, так что для доказательства теоремы достаточно научиться сравнивать параллельно все "суффиксы"двух -битовых чисел и , т. е. для каждого сравнить числа и .
Вспомним, что мы делали при сравнении чисел (скажем, длины). На нижнем уровне мы сравнивали биты:
На следующем уровне мы сравнивали двузначные числа
затем четырехзначные
и, наконец, восьмизначные:
Таким образом, для суффиксов длины, , и
результаты сравнения уже есть. Для суффикса длины результат можно получить, комбинируя результат сравнения
и . После этого у нас есть информация о суффиксах всех четных длин, и соединяя ее с информацией с первого этапа, получаем сведения про все суффиксы. Например, для сравнения суффиксов длины, то есть и , мы соединяем результаты сравнения и с результатами сравнения суффиксов длины , то есть и .
В общем случае картина такая: после "сужающегося дерева" мы строим "расширяющееся"; за шагов до конца мы знаем результаты сравнения всех суффиксов, длины которых кратны . Это дерево имеет размер и глубину , что завершает доказательство.
14. Покажите, что вычитание двух -битовых чисел по модулю выполняется схемой размера и глубины . (Указание: вычитание легко сводится к сложению, если заменить нули на единицы и наоборот.)
Теперь займемся умножением. Схема умножения двух -разрядных чисел имеет входов (по для каждого множителя) и выходов для произведения.
Посмотрим, какие оценки дает обычный способ умножения чисел столбиком. В нем умножение двух -разрядных чисел сводится к сложению копий первого числа (частично замененных на нули в зависимости от цифр второго числа) со сдвигами.
Получение этих копий требует схемы размера (общее число цифр в копиях) и глубины . Сложение двух -разрядных чисел мы можем выполнить с помощью схемы размера и глубины , так что необходимые сложений можно выполнить схемой размера и глубины (если складывать сначала попарно, потом результаты снова попарно и т. д.). Оказывается, этот результат можно улучшить. Наиболее экономные способы основаны на преобразовании Фурье (о них можно прочесть в книге [1]). С их помощью, например, можно построить схему умножения -битовых чисел, имеющую размер .
Эти методы далеко выходят за рамки нашего обсуждения, но два улучшения мы приведем.
Теорема 12. Существует схема умножения двух -разрядных чисел размера и глубины .
Как мы уже говорили, умножение двух -разрядных чисел сводится к сложению таких чисел, и остается выполнить такое сложение схемой размера и глубины . Ключевым моментом здесь является сведение сложения трех чисел к сложению двух с помощью простой схемы размера и глубины. В самом деле, пусть есть три числа , и . Если мы будем складывать отдельно в каждом разряде, то в разряде может накопиться любая сумма от до, то есть в двоичной записи от до . Сформируем из младших битов этих двухбитовых сумм число , а из старших (сдвинутых влево) — число . Тогда, очевидно, . Получение цифр числа и происходит параллельно во всех разрядах и требует размера и глубины.
Теперь, если надо сложить чисел, можно разбить их на тройки и из каждых трех чисел получить по два. В следующий круг, таким образом, выйдут чисел (примерно — граничные эффекты большой роли не играют). Их снова можно сгруппировать по тройкам и т. д. С каждым уровнем число слагаемых убывает в полтора раза, так что глубина схемы будет логарифмической. Каждое преобразование трех слагаемых в два требует схемы размера
и уменьшает число слагаемых на единицу, так что потребуется
таких преобразований. Итак, эта конструкция имеет общий размер и глубину . Надо только отметить, что в конце у нас получается не одно число, а два, и их напоследок надо сложить — что мы умеем делать с глубиной и размером .
15. Докажите, что схема, вычисляющая булеву функцию от аргументов, у которой ни один аргумент не является фиктивным, имеет размер не менее и глубину не менее , где — некоторая константа, зависящая от выбранного набора элементов. (Аргумент функции называют фиктивным, если от него значение функции не зависит.)
Эта задача показывает, что если в процессе умножения двух -разрядных чисел мы суммируем слагаемых размера, то оценки для размера и для глубины, полученные при доказательстве теоремы 12, существенно улучшить нельзя.
Однако никто не обязывает нас следовать традиционному способу умножения столбиком — отказавшись от него, мы можем уменьшить размер схемы.
Теорема 13. Существует схема умножения двух -разрядных чисел размера и глубины .
Начнем с такого замечания. Вычисляя произведение двух комплексных чисел
обычным способом, мы делаем четыре умножения. Но можно обойтись и тремя с помощью такого трюка: вычислить , и , а потом найти как разность .
Аналогичный фокус можно проделать и для целых чисел. Разобьем -битовое число на две -битовые части, то есть представим его в виде . Теперь запишем произведение двух таких чисел:
Теперь видно, что достаточно найти три произведения , и , чтобы определить все три слагаемых в правой части равенства. Получается, что умножение двух -разрядных чисел сводится к трем умножениям -разрядных и к нескольким сложениям и вычитаниям. (На самом деле при умножении на
сомножители могут быть -разрядными, но это не страшно, так как обработка лишнего разряда сводится к нескольким сложениям.)
Для размера схемы, таким образом, получается рекурсивная оценка
из которой следует, что . В самом деле, для умножения -разрядных чисел требуется дерево рекурсивных вызовов глубины и степени ветвления. Заметим, что размер схемы в вершине пропорционален числу складываемых битов. При переходе от одного уровня к следующему (более близкому к корню) размер слагаемых растет вдвое, а число вершин уменьшается втрое, поэтому общее число элементов на этом уровне уменьшается в полтора раза. Таким образом, при движении по уровням от листьев к корню получается убывающая геометрическая прогрессия со знаменателем , сумма которой всего лишь втрое превосходит ее первый член. Остается заметить, что число листьев равно .
Оценка глубины также очевидна: на каждом уровне мы имеем схему сложения глубины , а число уровней есть .
На этом мы завершаем знакомство со схемами из функциональных элементов, выполняющими арифметические операции. О них можно прочесть в главе 29 учебника Кормена, Лейзерсона и Ривеста [18]
и в книге Ахо, Хопкрофта и Ульмана [1].
Рассмотрим теперь функцию "голосования"(majority).Она имеет нечетное число аргументов, и значение ее равно или в зависимости от того, какое из двух значений чаще встречается среди входов.
Теорема 14. Существует схема размера и глубины , вычисляющая функцию голосования.
На самом деле можно даже вычислить общее число единиц среди входов. Это делается рекурсивно: считаем отдельно для каждой половины, потом складываем. Получается логарифмическое число уровней. На верхнем уровне надо складывать числа размера , на следующем— размера и так до самого низа, где складываются однобитовые числа (то есть биты входа). Какой средний размер складываемых чисел? Половина вершин в дереве приходится на нижний уровень (числа длины), четверть — на следующий (числа длины) и т. д. Вспоминая, что ряд сходится, видим, что средний размер складываемых чисел есть и общий размер схемы есть . А общая глубина есть , так как на каждом из
уровней стоит схема глубины .
Заметим, что хотя функция голосования монотонна, построенная схема ее вычисления содержит немонотонные элементы (поскольку операция сложения не монотонна). Мы уже говорили, что всякую монотонную функцию можно составить из конъюнкций и дизъюнкций. Для функции голосования есть очевидный способ это сделать: написать дизъюнкцию всех конъюнкций размера (напомним, что число входов предполагается нечетным). Однако при этом получится схема экспоненциального по размера.
Теорема 15. Существует схема размера и глубины , составленная только из элементов И и ИЛИ (с двумя входами), вычисляющая функцию голосования.
Для начала заметим, что ограничение на размер является следствием ограничения на глубину, так как элементы И и ИЛИ имеют только два входа и число элементов в схеме глубины
есть .
Схема будет строиться из элементов большинства с тремя входами. (Каждый из них можно собрать из конъюнкций и дизъюнкций по формуле .) Выход схемы будет большинством из трех значений, каждое из которых есть большинство из трех значений и т. д. (рис. 2.3).
Рис. 2.3. Дерево из элементов 3-большинства
Продолжая эту конструкцию на уровнях, мы получим схему с входами. (Отметим, что эта схема не будет вычислять большинство среди своих входов — по той же причине, по которой результат непрямого голосования может отличаться от мнения большинства.) Но мы сделаем вот какую странную вещь: возьмем
равным при достаточно большом коэффициенте пропорциональности (при этом число входов такой схемы будет полиномиально зависеть от ) и напишем на входах случайно выбранные переменные из данного нам набора . (Переменные, записываемые на разных входах, выбираются независимо.) Оказывается, что с ненулевой вероятностью эта схема будет вычислять функцию большинства среди , если константа достаточно велика. Следовательно, искомая схема существует.
Обратите внимание: нам удастся доказать существование интересующей нас схемы, не предъявив ее явно. (Такое использование вероятностных методов в комбинаторных рассуждениях часто бывает полезно.)
Итак, почему же схема с положительной вероятностью вычисляет функцию большинства? Это доказывается так: рассмотрим какой-то один набор значений на входах и докажем, что на этом конкретном наборе случайная схема выдает правильный ответ с вероятностью, очень близкой к единице (равной при очень малом).
Если число настолько мало, что остается меньшим единицы даже после умножения на число возможных входов (), то получаем требуемое (каждое из событий имеет вероятность не меньше , значит их пересечение имеет вероятность не меньше ).
Итак, осталось оценить вероятность того, что случайная схема даст правильный ответ на данном входе. Пусть доля единиц среди всех входов равна. Тогда на каждый входной провод схемы подается единица с вероятностью и нуль с вероятностью (выбор случайной переменной дает единицу с вероятностью ), причем сигналы на всех входах независимы.
Если на трех входах элемента -большинства сигналы независимы, и вероятность появления единицы на каждом входе есть , то вероятность появления единицы на выходе есть . На следующих уровнях вероятность появления единицы будет равна График функции на отрезке
(рис. 2.4) показывает, что при итерациях функции дисбаланс (отклонение от середины) нарастает и последовательность стремится к краю отрезка. Надо только оценить число шагов.
Рис. 2.4. Итерируемая функция
Если вначале единицы составляют большинство из аргументов (напомним, нечетно), то их как минимум , так что . Таким образом, начальный дисбаланс составляет как минимум . А в конце нам нужно приблизиться к краю отрезка на расстояние .
Итак, нам осталось доказать такую лемму (относящуюся скорее к математическому анализу):
Лемма. Пусть последовательность задана рекуррентной формулой , где
Пусть . Тогда последовательность монотонно возрастает и приближается к на расстояние за
шагов. [Симметричное утверждение верно и при .]
Идея доказательства: посмотрим на функцию вблизи точки и у краев отрезка. В точке производная больше , поэтому удаление от растет как геометрическая прогрессия, и точка перейдет какую-то фиксированную границу (например, ) не позднее чем за
шагов. Затем потребуется шагов, чтобы дойти, скажем, до . В единице первая производная функции равна нулю, поэтому расстояние до единицы каждый раз примерно возводится в квадрат, и потому для достижения погрешности потребуется шагов (как в методе Ньютона отыскания корня). Всего получается шагов, что и требовалось.
На самом деле справедливо гораздо более сильное утверждение: существует схема размера и глубины , состоящая только из элементов И и ИЛИ, которая имеет входов и выходов и осуществляет сортировку последовательности нулей и единиц (это означает, что на выходе столько же единиц, сколько на входе, причем выходная последовательность всегда невозрастающая). Ясно, что средний бит выхода в такой ситуации реализует функцию большинства.
При кажущейся простоте формулировки единственная известная конструкция такой схемы (сортирующая сеть AKS, придуманная Айтаи, Комлошом и Сцемереди сравнительно недавно, в 1983 году) весьма сложна, и появление какой-то более простой конструкции было бы замечательным достижением.
Многие нетривиальные результаты теории алгоритмов можно переформулировать в терминах сложности каких-то булевых функций. Например, есть вероятностный алгоритм проверки простоты большого числа (применяемый в системах шифрования для проверки простоты чисел из нескольких тысяч цифр). Используя этот алгоритм, можно доказать такой факт: существует схема проверки простоты -битового числа (на вход подаются цифр, на выходе появляется единица, если число простое, и нуль, если число составное), размер которой ограничен полиномом от.
Вернемся к общим утверждениям о схемах и формулах. Мы уже говорили, что с точки зрения измерения размера схемы и формулы — это разные вещи (схемы экономичнее, так как в них одинаковые подформулы учитываются только один раз). Оказывается, что размер формулы можно связать с глубиной схемы.
Будем называть размером формулы число логических связок в ней. Мы предполагаем, что формула использует конъюнкции, дизъюнкции и отрицания, и в схемах будем использовать такие же элементы. Напомним, что размером схемы мы называли число элементов, а сложностью булевой функции — минимальный размер схемы, ее вычисляющей. Сложность функции обозначалась (точнее , где — набор разрешенных функциональных элементов, но сейчас мы договорились использовать конъюнкции, дизъюнкции и отрицания и опускаем индекс ).
Минимальный размер формулы, выражающей функцию , будем обозначать . Очевидно, . Более интересно, однако, следующее утверждение, связывающее размер схемы с глубиной формулы. Обозначим через
минимальную глубину схемы, вычисляющей функцию .
Теорема 16. Имеют место оценки и (для некоторых констант и и для всех ). Другими словами, меры сложности и отличаются не более чем в константу раз.
Первая оценка очевидна: если мы скопируем повторяющиеся фрагменты схемы, чтобы развернуть ее в дерево, то глубина не изменится. Если она равна, то в полученном дереве будет не больше элементов и соответствующая формула имеет размер не более . (Напомним, что элементами являются конъюнкции, дизъюнкции и отрицания, и потому ветвление не больше.)
То же самое можно сказать индуктивно. Пусть глубина схемы равна . Выход схемы является выходом некоторого элемента. Тогда на его входы подаются булевы функции глубины не больше . По предположению индукции их можно записать формулами размера . Таких формул максимум две, так что общий размер не превосходит .
Вторая оценка сложнее. Если мы будем преобразовывать формулу в схему естественным образом (введя вспомогательную переменную для каждой подформулы), то глубина получившейся схемы может быть близка к размеру формулы, а не к его логарифму. Например, если формула имеет вид , то у нас получится цепочка элементов И, у которых каждый следующий подвешен к левому входу предыдущего, и глубина равна . Конечно, если использовать ассоциативность конъюнкции, скобки можно переставить и получить более сбалансированное дерево глубины примерно, как и требуется. Но как выполнить такое преобразование в случае произвольной формулы?
Обозначим данную нам формулу через . Выберем у нее некоторую подформулу (как именно, мы объясним позже). Рассмотрим формулу , которая получится, если вместо
подставить (ложь), а также формулу , которая получится, если подставить. Легко понять, что равносильна формуле
Если теперь удастся заменить формулы схемами глубины не больше , то для получится схема глубины не больше.
Такое преобразование полезно, если все три формулы
имеют заметно меньший размер, чем исходная формула .
Лемма. У любой формулы размера (при достаточно больших ) есть подформула размера от до .
Доказательство. Каждая формула есть конъюнкция двух подформул, дизъюнкция двух подформул или отрицание подформулы. Начав со всей формулы, будем переходить к ее подформулам, на каждом шаге выбирая из двух подформул наибольшую. Тогда на каждом шаге размер убывает не более чем в два раза, и потому мы не можем миновать промежуток , концы которого отличаются втрое. (На самом деле тут есть небольшая неточность: размер формулы может убывать чуть быстрее, чем вдвое, так как размер формулы на единицу больше суммы размеров частей, но у нас есть запас, поскольку концы промежутка отличаются втрое, а не вдвое.) Лемма доказана.
Выбирая подформулу с помощью этой леммы, мы гарантируем, что размер всех трех формул не превосходит размера исходной формулы (подстановка нуля или единицы может только уменьшить размер формулы — некоторые части можно будет выбросить).
Применим ко всем трем формулам , и тот же прием, выделим в них подформулы среднего размера и так далее, пока мы не спустимся до формул малого размера, которые можно записать в виде схем как угодно. В итоге получится дерево с логарифмическим числом уровней, на каждом из которых стоят схемы глубины, а в листьях находятся схемы глубины .
Другими словами, индукцией по размеру формулы, выражающей некоторую функцию, легко получить оценку .
16. Определим глубину формулы как максимальное число вложенных пар скобок; для единообразия будем окружать отрицание скобками и писать вместо . Покажите, что при этом не получится ничего нового: минимальная глубина формулы, записывающей некоторую функцию , совпадает с минимальной глубиной схемы, вычисляющей.
Определение формульной сложности зависит от выбора базиса. Оказывается, что здесь (в отличие от схемной сложности) выбор базиса может изменить более чем в константу раз.
17. Объясните, почему доказательство теоремы 7 не переносится на случай формул.
Так происходит с функцией (знак обозначает сложение по модулю). Эта функция имеет формульную сложность , если сложение по модулю входит в базис. Однако в базисе И, ИЛИ, НЕ она имеет большую сложность, как доказала Б.А.Субботовская. Идея доказательства такова: если заменить случайно выбранную переменную в формуле с конъюнкциями и дизъюнкциями на случайно выбранное значение или, то формула упростится (не только эта переменная пропадет, но с некоторой вероятностью пропадут и другие). Если делать так многократно, то от формулы останется небольшая часть — с другой стороны, эта часть все равно должна реализовывать сложение оставшихся аргументов по модулю.
18. Докажите, что функция большинства может быть вычислена не только схемой, но и формулой полиномиального размера, содержащей только связки И и ИЛИ.
19. Докажите, что значения и для одной булевой функции и различных полных базисов полиномиально связаны: существует полином (зависящий от выбора базисов), для которого при всех . (Указание: использовать теорему 16.)
