Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Посмотрите новые поступления ... Обратите внимание!
 
  Наука >> Математика >> Алгебра, математическая логика и теория чисел | Популярные статьи
 Написать комментарий  Добавить новое сообщение
 См. также

Популярные статьиМ.Н. Вялый "Сложность вычислительных задач": ШеньВерещагин

Up: Логические формулы и схемы Previous: 2. Полные системы связок Contents:

3. Схемы из функциональных элементов

Формулы представляют собой способ записи композиции функций. Например, если мы сначала применяем функцию $f$, а потом функцию $g$, это можно записать формулой $g(f(x))$. Но есть и другой способ: можно изобразить каждую функцию в виде прямоугольника с "входом" и "выходом" и соединить выход функции $f$ со входом функции $g$ (рис. 1).

Рис. 1. Два способа изобразить композицию
\begin{displaymath}
\unitlength=0.77mm
\begin{picture}(80,20)
\put(0,10){\line(1...
...g$}}
\put(70,10){\makebox(0,0)[cl]{$g(f(x))$}}
%
\end{picture}\end{displaymath}

Такое представление отнюдь не является чисто теоретическим. В течение нескольких десятков лет электронная промышленность выпускает микросхемы, которые выполняют логические операции. Такая микросхема имеет электрические контакты, напряжение на которых кодирует логические значения И и Л. Конкретное напряжение зависит от типа схемы, но обычно это единицы вольт, и высокий потенциал (относительно заземления) считается единицей, а низкий - нулем.

Одной из типичных схем является схема И-НЕ, она имеет два входа и один выход. Сигнал на выходе является отрицанием конъюнкции сигналов на входе. Другими словами, на выходе появляется высокий потенциал (сигнал $1$) тогда и только тогда, когда на одном из входов потенциал низкий ($0$). Из такой схемы легко получить схему НЕ (изменяющую уровень сигнала на противоположный), соединив проводом два входа. При этом на оба входа поступает один и тот же сигнал, и операция И его не меняет ($p\land p=p$), а НЕ меняет на противоположный. Взяв два элемента и используя второй из них в качестве элемента НЕ, меняющего сигнал с выхода первого элемента, получаем схему, которая реализует функцию И. А если поставить два элемента НЕ перед каждым из входов элемента И-НЕ, получим схему, реализующую функцию ИЛИ: $\lnot (\lnot
p\land\lnot q) \leftrightarrow (p\lor q)$.

Теорема 3 о полноте системы связок теперь гарантирует, что любую булеву функцию можно реализовать в виде схемы. Надо иметь в виду, однако, что предлагаемая в ее доказательстве конструкция (дизъюнктивная нормальная форма) имеет скорее теоретический интерес, поскольку приводит к схемам очень большого размера даже для простых функций (если число аргументов велико). Например, схема, сравнивающая два $16$-битовых числа, должна иметь $32$ входа и поэтому в ее реализации с помощью дизъюнктивной нормальной формы будет порядка $2^{32}$ элементов - что мало реально. (Между тем такую схему можно построить гораздо проще, из нескольких сотен элементов.)

Поэтому вопрос о том, сколько элементов нужно для реализации той или иной функции, представляет большой интерес - как практический, так и философский. (Одна из центральных проблем математики и информатики, так называемая "проблема перебора", может быть сформулирована в этих терминах.)

Мы сейчас дадим более формальное определение схемы и реализуемой ею булевой функции. Но прежде всего ответим на такой вопрос - почему мы вообще говорим о схемах? Ведь можно записать композицию булевых функций в виде формулы, не будет ли это то же самое?

Оказывается, не совсем, и разницу легко видеть на примере (рис. 2).

Рис. 2. Элемент входит в формулу дважды
\begin{figure}\begin{displaymath}
\unitlength=0.68mm
\begin{picture}(140,50)
\pu...
...)[cl]{$h(g_1(f(x)), g_2(f(x)))$}}
%
\end{picture} \end{displaymath}\end{figure}

Здесь один и тот же элемент схемы ($f$) приходится указывать в формуле дважды, поскольку его выход используется в качестве входа двух других элементов. Схемы, в которых такого ветвления нет (на практике оно вполне возможно, хотя и ограничено "нагрузочной способностью выхода", как говорят инженеры), как раз и соответствуют формулам. Но в общем случае формула может быть длинной, даже если схема содержит небольшое число элементов, поскольку число копий может расти экспоненциально с ростом глубины схемы.

Хотя идея образования схемы из функциональных элементов, реализующих булевы функции, достаточно наглядна, дадим более формальное определение. Пусть имеется $n$ булевых переменных $x_1,\dots,x_n$, называемых входами. Пусть также имеется некоторое число переменных $y_1,\dots,y_m$, называемых проводниками. Пусть для каждого проводника схемы задана булева функция из некоторого множества $B$, выражающая его значение через другие проводники и входы. При этом требуется, чтобы не было циклов (когда $y_i$ зависит от $y_j$, которое зависит от $y_k$, ..., которое зависит от $y_i$). Пусть, кроме того, среди проводников выделен один, называемый выходом. В таком случае говорят, что задана схема размера $m$ из функциональных элементов в базисе $B$ с $n$ входами. (С точки зрения инженера размер - это число использованных элементов, а базис $B$ - это ассортимент доступных ему элементов.)

Отсутствие циклов гарантирует, что есть проводник, зависящий только от входов (иначе можно было бы прийти к циклу: возьмем какой-то проводник, затем возьмем тот проводник, от которого он зависит, и т.д.). Его значение, таким образом, однозначно определяется сигналами на входах. Среди оставшихся проводников также нет цикла, поэтому можно найти один из них, зависящий только от уже известных, и определить его значение. Перенумеровав проводники в таком порядке, мы можем записать последовательность присваиваний (программу)

\begin{displaymath}
\begin{aligned}
y_1&:= f_1(\dots);\\
y_2&:= f_2(\dots);\\
&\dots\\
y_m&:= f_m(\dots);\\
\end{aligned} \end{displaymath}

в правых частях которых стоят функции из $B$, примененные ко входам и уже найденным значениям. При этом можно считать, что результат схемы есть $y_m$ (все последующие присваивания уже не нужны). Такая программа определяет $y_m$ при известных значениях входов и тем самым вычисляет некоторую булеву функцию.

Набор булевых функций $B$ называется полным, если любая булева функция может быть задана схемой из $B$- элементов (существует программа, ее вычисляющая, при этом в правых частях присваиваний стоят функции из $B$). Ясно, что это равносильно возможности записать булеву функцию в виде формулы со связками из $B$ (как мы говорили, разница только в том, что один и тот же элемент будет фигурировать в формуле многократно).

Сложностью булевой функции $f$ относительно $B$ называется минимальный размер схемы из $B$- элементов, вычисляющей функцию $f$. Этот размер будем обозначать $\size _B(f)$.

Теорема 7.   Пусть $B_1$ и $B_2$ - два полных набора булевых функций. Тогда соответствующие им сложности отличаются не более чем на постоянный множитель: найдется такое число $C$, что $\size _{B_1}(f)\le
C\size _{B_2}(f)$ и $\size _{B_2}(f)\le C\size _{B_1}(f)$ для любой функции $f$.

Доказательство. Утверждение почти очевидно: поскольку наборы $B_1$ и $B_2$ полны, то каждая функция одного из наборов может быть вычислена какой- то программой, составленной из функций другого набора. Теперь можно взять в качестве $C$ наибольшую длину таких программ, и неравенства будут выполняться: каждую строку программы можно заменить на $C$ (или меньше) строк с использованием функций другого набора. $ \qedsymbol$

Что можно сказать о сложности произвольной булевой функции от $n$ аргументов? Следующая теорема показывает, что она экспоненциально зависит от $n$ (для "наугад взятой" функции).

Теорема 8.   а) Сложность любой булевой функции от $n$ аргументов не превосходит $С^n$ для некоторого константы $C$. б) Сложность большинства булевых функций от $n$ аргументов не меньше $c^n$ для некоторой константы $c$.

Доказательство. Первое утверждение очевидно: размер схемы, реализующей дизъюнктивную нормальную форму, есть $O(n2^n)$ (имеется не более $2^n$ конъюнктов размера $O(n)$).

Чтобы доказать второе утверждение, оценим число различных схем с $n$ аргументами размера $N$. Каждая такая схема может быть описана последовательностью из $N$ присваиваний, выражающих одну из переменных через предыдущие. Для каждой формулы есть не более $3(N+n)^2$ вариантов (три типа операций - конъюнкция, дизъюнкция, отрицание, и каждый из не более чем двух аргументов выбирается среди не более чем $N+n$ вариантов). Отсюда легко получить оценку $2^{O(N\log N)}$ на число всех функций сложности не более $N$ (считая $N\ge n$).

Всего булевых функций с $n$ аргументами имеется $2^{2^n}$. Из сравнения этих формул видно, что что при $c<2$ и при достаточно больших $n$ булевы функции сложности меньше $c^n$ составляют меньшинство, так как $
2^{O(c^n\log c^n)}
$ много меньше $2^{2^n}$. (Уменьшая константу $c$, можно добиться, чтобы они составляли меньшинство при всех $n$, а не только достаточно больших.) $ \qedsymbol$

Эта теорема, однако, ничего не говорит о сложности конкретных булевых функций. Ситуация здесь такова. Есть разнообразные методы и приемы получения верхних оценок. Но про нижние оценки неизвестно практически ничего. Про многие функции мы подозреваем, что их сложность велика (экспоненциальна), но доказать это пока не удается. Весьма нетривиальные идеи позволяют доказывать экспоненциальные нижние оценки для некоторых специальных классов схем, например, схем из монотонных элементов или схем ограниченной глубины (использующих элементы И и ИЛИ с произвольным числом входов). Получение экспоненциальных оценок для более общих схем - один из возможных подходов к знаменитой проблеме перебора, центральной проблеме теории сложности вычислений.

Мы не будем углубляться в эту теорию, а приведем лишь несколько верхних оценок для конкретных задач. При этом мы не претендуем на полноту, а хотим лишь показать несколько интересных идей и приемов.

Рассмотрим уже упоминавшуюся функцию сравнения двух $n$- битовых чисел. Она имеет $2n$ аргументов ($n$ для одного числа и $n$ для другого). Обозначим эту функцию $\comp _n$.

Теорема 9.   Пусть $B$ - полный набор функций. Существует такая константа $C$, что $\size _B(\comp _n)\le Cn$.

Доказательство. Заметим, что поскольку в формулировке теоремы оценка размера проводится с точностью до константы, то выбор конкретного базиса не имеет значения. Другими словами, мы можем предполагать, что любое конечное число необходимых нам функций в этом базисе есть.

Схема сравнения чисел будет рекурсивной (чтобы сравнить два числа, мы отдельно сравниваем их левые и правые половины, а затем объединяем результаты). При этом, как часто бывает, надо усилить утверждение, чтобы индукция прошла. А именно, мы будем строить схему с $2n$ входами $x_1,\dots,x_n,y_1,\dots,y_n$ и двумя выходами, которая указывает, какой из трех случаев $x<y$, $x=y$ или $x>y$ имеет место. (Здесь $x$ - число, записываемое в двоичной системе как $x_1\dots x_n$). Два выходных бита кодируют четыре возможности, а нужно только три, так что есть некоторый запас. Для определенности можно считать, что первый выходной бит истинен, если числа равны, а второй - если $x<y$. Тогда возможны три варианта сигналов на выходе: $10$ (равенство), $01$ (при $x<y$) и $00$ (при $x>y)$.

Объясним теперь, как собрать, скажем, схему сравнения двух $16$- битовых чисел. Соберем отдельно схему сравнения старших $8$ битов и младших $8$ битов. Каждая из них даст ответ в форме двух битов. Теперь из этих четырех битов надо собрать два. (Если в старших разрядах неравенство, то оно определяет результат сравнения; если старшие разряды равны, то результат сравнения определяется младшими разрядами.) Написанная в скобках фраза определяет булеву функцию с четырьмя битами на входе и двумя битами на выходе, и может быть реализована некоторой схемой фиксированного размера. Таким образом, если через $T(n)$ обозначить размер схемы, сравнивающей $n$- битовые числа, то получаем оценку

\begin{displaymath}
T(2n)\le 2T(n)+c,
\end{displaymath}

где $c$ - некоторая константа, зависящая от выбора базиса. Отсюда следует, что $T(2^k)\le c'2^k$ при некотором $c'$. В самом деле, для достаточно большого $c'$ можно доказать по индукции, что

\begin{displaymath}
T(m) \le c'm - c
\end{displaymath}

(мы должны усилить неравенство, вычтя из правой части $c$, чтобы индуктивный шаг прошел; база индукции остается верной, если $c'$ достаточно велико).

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

Каждая внутренняя вершина и каждый лист (где сравниваются два бита) представляют собой схемы ограниченного размера, откуда и вытекает оценка $T(2^k)\le c'2^k$.

Осталось лишь сказать, что делать, если размер чисел (который мы обозначали через $n$) не есть точная степень двойки. В этом случае можно увеличить размер до ближайшей сверху степени двойки (не более чем в два раза) и подать на старшие разряды входов нули. Оба действия приводят к увеличению размера схемы не более чем в константу раз. $ \qedsymbol$

Теперь рассмотрим задачу о сложении двух $n$-битовых чисел. (Строго говоря, тут возникает не булева функция, а функция $\bbB ^n\times\bbB ^n\to\bbB ^{n+1}$, но все наши определения очевидно переносятся на этот случай.)

Теорема 10.   Существует схема сложения двух $n$- битовых чисел размера $O(n)$.

Доказательство. Напомним смысл обозначения $O(n)$: нам надо построить схему сложения $n$- битовых чисел, имеющую размер не более $cn$ для некоторого $c$ и для всех $n$.

Это совсем просто. Посмотрим на сложение в столбик:

\begin{displaymath}
\begin{array}{rrrrr}
& 0 & 1 & 1 & \\
& 1 & 0 & 0 &1\\
& 1 & 0 & 1 &1\\
\hline
1 & 0 & 1 & 0 &0\\
\end{array} \end{displaymath}

Верхняя строка - биты переноса, нижняя - результат. Заметим, что каждый из битов переноса или результата определяется тремя другими битами (бит результата равен сумме двух битов слагаемых и бита переноса по модулю $2$, а бит переноса равен $1$, если хотя бы два из этих трех битов равны $1$). Поэтому можно составить схему, которая вычисляет эти биты справа налево и имеет размер $n$. $ \qedsymbol$

Заметим, что предыдущее утверждение (теорема 9) является следствием этого: чтобы сравнить числа $x$ и $y$, сложим число $(2^n-1)-x$ (то есть число $x$, в котором все единицы заменены нулями и наоборот) и число $y$. Если в старшем разряде появится единица, значит, $y>x$, а если нет, то $y\le x$. Остается заметить, что и сложение, и обращение битов в числе $x$ реализуются схемами линейного размера.

Тем не менее конструкция, использованная при доказательстве теоремы 9, имеет некоторые преимущества. Назовем глубиной схемы максимальное число элементов на пути от входа к выходу. Если представить себе, что сигнал на выходе элемента появляется не сразу после подачи сигналов на входы, а с некоторой задержкой, то глубина схемы определяет суммарную задержку. Легко понять, что рекурсивная схема сравнения имела глубину $O(\log n)$ (число уровней пропорционально логарифму размера входа), в то время как построенная только что схема сложения имеет глубину, пропорциональную $n$ (биты переноса вычисляются последовательно, справа налево). Но можно соединить эти два результата:

Теорема 11.   Существует схема сложения двух $n$- битовых чисел размера $O(n)$ и глубины $O(\log n)$.

Доказательство. Как мы видели, проблема в том, что биты переноса вычисляются последовательно, а не параллельно. Если удастся их все вычислить схемой размера $O(n)$ и глубины $O(\log n)$, то дальнейшее очевидно.

Как мы уже говорили, вычисление битов переноса равносильно сравнению, так что достаточно научиться сравнить параллельно все "суффиксы" чисел,  -е для каждого $i$ сравнить числа $x_ix_{i+1}\dots x_n$ и $y_iy_{i+1}\dots y_n$.

Вспомним, что мы делали при сравнении чисел (скажем, длины $8$). На нижнем уровне мы сравнивали биты:

\begin{displaymath}
\begin{array}{cccccccc}
x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & ...
... \\
y_1 & y_2 & y_3 & y_4 & y_5 & y_6 & y_7 & y_8
\end{array} \end{displaymath}

На следующем уровне мы сравнивали двузначные числа

\begin{displaymath}
\begin{array}{cccc}
x_1 x_2 & x_3 x_4 & x_5 x_6 & x_7 x_8 \\
y_1 y_2 & y_3 y_4 & y_5 y_6 & y_7 y_8
\end{array} \end{displaymath}

затем четырехзначные

\begin{displaymath}
\begin{array}{cc}
x_1 x_2 x_3 x_4 & x_5 x_6 x_7 x_8 \\
y_1 y_2 y_3 y_4 & y_5 y_6 y_7 y_8
\end{array} \end{displaymath}

и, наконец, восьмизначные:

\begin{displaymath}
\begin{array}{c}
x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 \\
y_1 y_2 y_3 y_4 y_5 y_6 y_7 y_8
\end{array} \end{displaymath}

Таким образом, для суффиксов длины $8$, $4$, $2$ и $1$ результаты сравнения уже есть. Для суффикса длины $6$ результат можно получить, комбинируя результат сравнения $x_3x_4 ? y_3y_4$ и $x_5x_6x_7x_8 ? y_5y_6y_7y_8$. После этого у нас есть информация о суффиксах всех четных длин, и соединяя ее с информацией с первого этапа, получаем сведения про все суффиксы. Например, для сравнения суффиксов длины $7$, то есть $x_2\dots x_8$ и $y_2\dots y_8$, мы соединяем результаты сравнения $x_2$ и $y_2$ с результатами сравнения суффиксов длины $6$, то есть $x_3\dots x_8$ и $y_3\dots y_8$.

В общем случае картина такая: после "сужающегося дерева" мы строим "расширяющееся"; за $k$ шагов до конца мы знаем результаты сравнения всех суффиксов, длины которых кратны $2^k$. Это дерево имеет размер $O(n)$ и глубину $O(\log n)$, что завершает доказательство. $ \qedsymbol$

Задача 12.   Показать, что вычитание двух $n$- битовых чисел по модулю $2^n$ выполняется схемой размера $O(n)$ и глубины $O(\log n)$. (Указание: вычитание легко сводится к сложению, если заменить нули на единицы и наоборот.)

Теперь займемся умножением. Схема умножения двух $n$- битовых чисел имеет $2n$ входов (по $n$ для каждого множителя) и $2n$ выходов для произведения.

Посмотрим, какие оценки дает обычный способ умножения чисел столбиком. В нем умножение двух $n$- разрядных чисел сводится к сложению $n$ копий первого числа (частично замененных на нули в зависимости от цифр второго числа) со сдвигами.

Получение этих копий требует схемы размера $O(n^2)$ (общее число цифр в копиях) и глубины $O(1)$. Сложение двух $n$- разрядных чисел мы можем выполнить с помощью схемы размера $O(n)$ и глубины $O(\log n)$, так что необходимые $n-1$ сложений можно выполнить схемой размера $O(n^2)$ и глубины $O(\log^2 n)$ (если складывать сначала попарно, потом результаты снова попарно и т.д.). Оказывается, этот результат можно улучшить. Наиболее экономные способы основаны на преобразовании Фурье и далеко выходят за рамки нашего обсуждения, но два улучшения мы приведем.

Теорема 12.   Существует схема умножения двух $n$- битовых чисел размера $O(n^2)$ и глубины $O(\log n)$.

Доказательство. Как мы уже говорили, умножение двух $n$- битовых чисел сводится к сложению $n$ таких чисел, и остается выполнить такое сложение схемой размера $O(n^2)$ и глубины $O(\log n)$. Ключевым моментом здесь является сведение сложения трех чисел к сложению двух с помощью простой схемы размера $O(n)$ и глубины $O(1)$. В самом деле, пусть есть три числа $x$, $y$ и $z$. Если мы будем складывать отдельно в каждом разряде, то в разряде может накопиться любая сумма от $0$ до $3$, то есть в двоичной записи от $00$ до $11$. Сформируем из младших битов этих двухбитовых сумм число $u$, а из старших (сдвинутых влево) - число $v$. Тогда, очевидно, $x+y+z=u+v$. Получение цифр числа $u$ и $v$ происходит параллельно во всех разрядах и требует размера $O(n)$ и глубины $O(1)$.

Теперь, если надо сложить $n$ чисел, можно разбить их на тройки и из каждых трех чисел получить по два. В следующий круг, таким образом, выйдут $(2/3)n$ чисел (примерно - граничные эффекты большой роли не играют). Их снова можно сгруппировать по тройкам и т.д. Получается дерево, в котором размеры уровней образуют геометрическую прогрессию со знаменателем $3/2$, поэтому глубина этого дерева логарифмическая. Число вершин в нем (считая за вершину преобразование трех чисел в два) будет примерно $n$, так как при каждом преобразовании число слагаемых уменьшается на единицу. Итак, эта конструкция имеет общий размер $O(n^2)$ и глубину $O(\log n)$. Надо только отметить, что в конце у нас получается не одно число, а два, и их напоследок надо сложить - что мы умеем делать с глубиной $O(\log n)$ и размером $O(n)$. $ \qedsymbol$

Задача 13.   Доказать, что схема, вычисляющая булеву функцию $f$ от $n$ аргументов, у которой ни один аргумент не является фиктивным, имеет размер не менее $cn$ и глубину не менее $c\log n$ (где $c$ - некоторая константа, зависящая от выбранного набора элементов). (Аргумент функции называют фиктивным, если при его изменении значение функции не меняется.)

Эта задача показывает, что если в процессе умножения двух $n$- битовых чисел мы суммируем $n$ слагаемых, то оценки $O(n^2)$ для размера и $O(\log n)$ для глубины, полученные при доказательстве теоремы 12, существенно улучшить нельзя.

Однако никто не обязывает нас следовать традиционному способу умножения столбиком - отказавшись от него, мы можем уменьшить размер схемы.

Теорема 13.   Существует схема умножения двух $n$- битовых чисел размера $O(n^{\log_2 3})$ и глубины $O(\log^2 n)$.

Доказательство. Начнем с такого замечания. Вычисляя произведение двух комплексных чисел

\begin{displaymath}
(a+bi)(c+di)=(ac-bd)+(ad+bc)i
\end{displaymath}

обычным способом, мы делаем четыре умножения. Но можно обойтись и тремя с помощью такого трюка: вычислить $ac$, $bd$ и $(a+b)(c+d)$, а потом найти $ad+bc$ как разность $(a+b)(c+d)-ac-bd$.

Аналогичный фокус можно проделать и для целых чисел. Разобьем $2n$- битовое число на две $n$- битовые части, то есть представим его в виде $a2^n+b$. Теперь запишем произведение двух таких чисел:

\begin{displaymath}
(a2^n+b)(c2^n+d)=ac2^{2n}+(ad+bc)2^n+bd.
\end{displaymath}

Отсюда видно, что для определения всех трех слагаемых в правой части равенства достаточно найти три произведения $ac$, $bd$ и $(a+b)(c+d)$. Получается, что умножение двух $2n$- битовых чисел сводится к трем умножениям $n$- битовых и к нескольким сложениям и вычитаниям. (На самом деле при умножении $(a+b)$ на $(c+d)$ сомножители могут быть $(n+1)$- битовыми, но это не страшно, так как обработка лишнего разряда соответствует нескольким сложениям.)

Для размера схемы, таким образом, получается рекурсивная оценка

\begin{displaymath}
S(2n)\le 3S(n)+O(n),
\end{displaymath}

из которой следует, что $S(n)=O(n^{\log_2 3})$. (В самом деле, для умножения $n$- битовых чисел получается дерево рекурсивных вызовов глубины $\log_2 n$ и степени ветвления $3$, так что число его листьев и общее число вершин есть $O(3^{\log_2
n})=O(n^{\log_2 3})$. Остается понять только, что средний размер схемы в каждой вершине есть $O(1)$. В самом деле, он пропорционален числу складываемых битов. При переходе от одного уровня к следующему (более близкому к корню) число битов растет вдвое, а число вершин уменьшается втрое, поэтому общее число элементов на этом уровне уменьшается в полтора раза. Таким образом, при движении по уровням от листьев к корню получается убывающая геометрическая прогрессия со знаменателем $2/3$, сумма которой всего лишь втрое превосходит ее первый член.

Оценка глубины также очевидна: на каждом уровне мы имеем схему сложения глубины $O(\log n)$, а число уровней есть $O(\log n)$. $ \qedsymbol$

Рассмотрим теперь функцию голосования (majority). Она имеет нечетное число аргументов, и значение ее равно $0$ или $1$ в зависимости от того, какое из двух значений чаще встречается среди входов.

Теорема 14.   Существует вычисляющая функцию голосования схема размера $O(n)$ и глубины $O(\log n\log\log n)$.

Доказательство. На самом деле можно даже вычислить общее число единиц среди входов. Это делается рекурсивно: считаем отдельно для каждой половины, потом складываем. Получается логарифмическое число уровней. На верхнем уровне надо складывать числа размера $\log
n$, на следующем - размера $\log n -1$ и так до самого низа, где складываются однобитовые числа (то есть биты входа). Какой средний размер складываемых чисел? Половина вершин в дереве приходится на нижний уровень (числа длины $1$), четверть - на следующий (числа длины $2$) и т.д. Вспоминая, что ряд $\sum
(k/2^k)$ сходится, видим, что средний размер складываемых чисел есть $O(1)$ и общий размер схемы есть $O(n)$. А общая глубина есть $O(\log n\log\log n)$, так как на каждом из $\log
n$ уровней стоит схема глубины $O(\log\log n)$. $ \qedsymbol$

Заметим, что построенная схема вычисления функции голосования содержит в себе немонотонные элементы (поскольку операция сложения не монотонна). Мы уже говорили, что всякую монотонную функцию можно составить из конъюнкций и дизъюнкций. Для функции голосования есть очевидный способ это сделать: написать дизъюнкцию всех конъюнкций размера $(n+1)/2$ (напомним, что число входов $n$ предполагается нечетным). Однако при этом получится схема экспоненциального по $n$ размера.

Теорема 15.   Существует схема размера $O(n^c)$ и глубины $O(\log n)$, составленная только из элементов И и ИЛИ (с двумя входами), вычисляющая функцию голосования.

Доказательство. Для начала заметим, что ограничение на размер является следствием ограничения на глубину, так как элементы И и ИЛИ имеют только два входа и число входов схемы глубины $d$ есть $O(2^d)$.

Схема будет строиться из элементов большинства с тремя входами ($3$-большинства). Каждый из них можно собрать из конъюнкций и дизъюнкций по формуле $(a\land b)\lor (a\land c)\lor (b\land c)$. Выход схемы будет большинством из трех значений, каждое из которых есть большинство из трех значений и т.д. (рис. 3).

Рис. 3. Дерево из элементов $3$-большинства
\begin{figure}\begin{displaymath}
\unitlength=0.5mm
\begin{picture}(80,50)
%
\p...
...t(34,50){\dots}
\put(64,50){\dots}
%
\end{picture}\end{displaymath}\end{figure}

Продолжая эту конструкцию на $k$ уровнях, мы получим схему с $3^k$ входами. (Отметим, что эта схема не будет вычислять большинство среди своих входов - по той же причине, по которой результат непрямого голосования может отличаться от мнения большинства.) Но мы сделаем вот какую странную вещь: возьмем $k$ равным $c\log n$ при достаточно большом коэффициенте пропорциональности $c$ (при этом число входов такой схемы будет полиномиально зависеть от $n$) и напишем на входах случайно выбранные переменные из данного нам набора $x_1,\dots,x_n$. (Переменные, записываемые на разных входах, выбираются независимо.) Оказывается, что с ненулевой вероятностью эта схема будет вычислять функцию большинства среди $x_1,\dots,x_n$, если константа $c$ достаточно велика. Следовательно, искомая схема существует.

Обратите внимание: нам удастся доказать существование интересующей нас схемы, не предъявив ее явно. (Такое использование вероятностных методов в комбинаторных рассуждениях часто бывает полезно.)

Итак, почему же схема с положительной вероятностью вычисляет функцию большинства? Это доказывается так: рассмотрим какой-то один набор значений на входах и докажем, что на этом конкретном наборе случайная схема выдает правильный ответ с вероятностью, очень близкой к единице (равной $1-\varepsilon$ при очень малом $\varepsilon$).

Если число $\varepsilon$ настолько мало, что остается меньшим единицы даже после умножения на число возможных входов ($2^n$), то получаем требуемое (каждое из $2^n$ событий имеет вероятность не меньше $1-\varepsilon$, значит их пересечение имеет вероятность не меньше $1-2^n\varepsilon>0$).

Итак, осталось оценить вероятность того, что случайная схема даст правильный ответ на данном входе. Пусть доля единиц среди всех входов равна $p$. Тогда на каждый входной провод схемы подается единица с вероятностью $p$ и нуль с вероятностью $1-p$ (выбор случайной переменной дает единицу с вероятностью $p$), причем сигналы на всех входах независимы.

Если на трех входах элемента $3$-большинства сигналы независимы, и вероятность появления единицы на входе есть $p$, то вероятность появления единицы на выходе есть $\varphi(p)=3p^2(1-p)+p^3=3p^2-2p^3$. На следующих уровнях вероятность появления единицы будет равна

\begin{displaymath}\varphi(\varphi(p)),\varphi(\varphi(\varphi(p))),\dots\end{displaymath}

График функции $\varphi(x)$ на отрезке $[0,1]$ (рис. 4) показывает, что при итерациях функции $\phi$ дисбаланс (отклонение от середины) нарастает. Поэтому последовательность итераций стремится к краю отрезка. Надо только оценить число шагов.

Рис. 4. Итерируемая функция $\varphi $
\begin{figure}%%\begin{center}
\epsfbox{logic.1}\end{center} %%
%%
\end{figure}

Если вначале единицы составляют большинство из $n$ аргументов (напомним, $n$ нечетно), то их как минимум $(n+1)/2$, так что $p\ge (n+1)/2n=1/2+1/(2n)$. Таким образом, начальный дисбаланс составляет как минимум $1/2n$. А в конце нам нужно приблизиться к краю отрезка на расстояние $2^{-n}$.

Итак, нам осталось доказать такую лемму (относящуюся скорее к математическому анализу):

Лемма .   Пусть функция $\varphi:[0,1]\to[0,1]$ задана формулой

\begin{displaymath}
\varphi(x)=3x^2-2x^3.
\end{displaymath}

Пусть последовательность $x_k$ определена рекуррентной формулой $x_{k+1}=\varphi(x_k)$. Пусть $x_0\ge1/2+1/(2n)$. Тогда последовательность $x_k$ монотонно возрастает и приближается к $1$ на расстояние $2^{-n}$ за $O(\log n)$ шагов.

Набросок доказательства: посмотрим на поведение функции в неподвижных точках. В окрестности точки $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)$ шагов, что и требовалось.

$ \qedsymbol$

На самом деле справедливо гораздо более сильное утверждение: существует схема размера $O(n\log n)$ и глубины $O(\log n)$, состоящая только из элементов И и ИЛИ, которая имеет $n$ входов и $n$ выходов и осуществляет сортировку (это означает, что на выходе столько же единиц, сколько на входе, причем выходная последовательность всегда невозрастающая). Ясно, что средний бит выхода в такой ситуации реализует функцию большинства.

При кажущейся простоте формулировки единственная известная конструкция такой схемы (сортирующая сеть AKS, придуманная Айтаи, Комлошом и Сцемереди сравнительно недавно, в 1983 году1) весьма сложна, и появление какой-то более простой конструкции было бы замечательным достижением.

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

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

Будем называть размером формулы число логических связок в ней. Мы предполагаем, что формула использует конъюнкции, дизъюнкции и отрицания, и в схемах будем использовать такие же элементы. Напомним, что размером схемы мы называли число элементов, а сложностью булевой функции - минимальный размер схемы, ее вычисляющей. Сложность функции $h$ обозначалась $\size (h)$ (точнее $\size _B(h)$, где $B$ - набор разрешенных функциональных элементов, но сейчас мы договорились использовать конъюнкции, дизъюнкции и отрицания и опускаем индекс $B$).

Минимальный размер формулы, выражающей функцию $h$, будем обозначать $\fsize (h)$. Очевидно, $\size (h)\le \fsize (h)$. Более интересно, однако, следующее утверждение, связывающее размер схемы с глубиной формулы. Обозначим через $\depth (h)$ минимальную глубину схемы, вычисляющей функцию $h$.

Теорема 16.   Имеют место оценки $\fsize (h)\le c_1^{\depth (h)}$ и $\depth (h)\relax \le c_2\log\fsize (h)$ (для некоторых констант $c_1$ и $c_2$ и для всех $h$). Другими словами, меры сложности $\depth $ и $\log\fsize $ отличаются не более чем в константу раз.

Доказательство. Первая оценка очевидна: если мы скопируем повторяющиеся фрагменты схемы, чтобы развернуть ее в дерево, то глубина не изменится. Если она равна $k$, то в полученном дереве будет не больше $2^k-1$ элементов (напомним, что элементами являются конъюнкции, дизъюнкции и отрицания, и потому ветвление не больше $2$). То же самое можно сказать индуктивно. Пусть глубина схемы равна $k$. Выход схемы является выходом некоторого элемента. Тогда на его входы подаются булевы функции глубины не больше $k-1$. По предположению индукции их можно записать формулами размера $2^{k-1}-1$. Таких формул максимум две, так что общий размер не превосходит $2(2^{k-1}-1)+1=2^k-1$.

Вторая оценка более сложна. Если мы будем преобразовывать формулу в схему естественным образом (введя по переменной для каждой подформулы), то глубина получившейся схемы может быть близка к размеру формулы, а не к его логарифму. Например, если формула имеет вид $(\ldots((p_1\land p_2)\land p_3)\land\dots
p_n)$, то у нас получится цепочка элементов И, у которых каждый следующий подвешен к левому входу предыдущего, и глубина есть $n-1$. Конечно, если использовать ассоциативность конъюнкции, скобки можно переставить и получить более сбалансированное дерево глубины примерно $\log
n$, как и требуется. Но как выполнить такое преобразование в случае произвольной формулы?

Обозначим данную нам формулу через $F$. Выберем у нее некоторую подформулу $G$ (как именно, мы объясним позже). Рассмотрим формулу $F_0$, которая получится, если вместо $G$ подставить $0$ (ложь), а также формулу $F_1$, которая получится, если подставить $1$. Легко понять, что $F$ равносильна формуле

\begin{displaymath}
((F_0 \land\lnot G)\lor (F_1\land G)).
\end{displaymath}

Если теперь удастся заменить формулы $F_0, F_1, G$ схемами глубины не больше $k$, то для $F$ получится схема глубины не больше $k+3$.

Такое преобразование полезно, если все три формулы $F_1, F_0, G$ имеют заметно меньший размер, чем исходная формула $F$.

Лемма .   У любой формулы размера $n$ (при достаточно больших $n$) есть подформула размера от $n/4$ до $3n/4$.

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

Выбирая подформулу $G$ с помощью этой леммы, мы гарантируем, что размер всех трех формул $F_0, F_1, G$ не превосходит $3/4$ размера исходной формулы (подстановка нуля или единицы может только уменьшить размер формулы - некоторые части можно будет выбросить).

Применим ко всем трем формулам $F_0$, $F_1$ и $G$ тот же прием, выделим в них подформулы среднего размера и так далее, пока мы не спустимся до формул малого размера, которые можно записать в виде схем как угодно. В итоге получится дерево с логарифмическим числом уровней, на каждом из которых стоят схемы глубины $3$, а в листьях находятся схемы глубины $O(1)$.

Другими словами, индукцией по размеру формулы, выражающей некоторую функцию $h$, легко получить оценку $\depth (h)=O(\log\fsize (h))$. $ \qedsymbol$

Задача 14.   Определим глубину формулы как максимальное число вложенных пар скобок; для единообразия будем окружать отрицание скобками и писать $(\lnot A)$ вместо $\lnot A$. Покажите, что при этом не получится ничего нового: минимальная глубина формулы, записывающей некоторую функцию $f$, совпадает с минимальной глубиной схемы, вычисляющей $f$.

Определение формульной сложности $\fsize (h)$ зависит от выбора базиса. Оказывается, что здесь (в отличие от схемной сложности) выбор базиса может изменить $\fsize (h)$ более чем в константу раз.

Задача 15.   Объясните, почему доказательство теоремы 7 не переносится на случай формул.

Пример такого рода доставляет функция $p_1\oplus
p_2\oplus\ldots\oplus p_n$ (знак $\oplus$ обозначает сложение по модулю $2$). Эта функция имеет формульную сложность $O(n)$, если сложение по модулю $2$ входит в базис. Однако в базисе И, ИЛИ, НЕ она имеет большую сложность, как доказала Б.А.Субботовская. Идея доказательства такова: если заменить случайно выбранную переменную в формуле с конъюнкциями и дизъюнкциями на случайно выбранное значение $0$ или $1$, то формула упростится (не только эта переменная пропадет, но с некоторой вероятностью пропадут и другие). Если делать так многократно, то от формулы останется небольшая часть - с другой стороны, эта часть все равно должна реализовывать сложение оставшихся аргументов по модулю $2$.

Задача 16.   Доказать, что функция большинства может быть вычислена не только схемой, но и формулой полиномиального размера, содержащей только связки И и ИЛИ.

Задача 17.   Доказать, что значения $\fsize _1(h)$ и $\fsize _2(h)$ для одной булевой функции $h$ и различных полных базисов полиномиально связаны: существует полином $P$ (зависящий от выбора базисов), для которого $\fsize _2 (h) \le P(\fsize _1(h))$ при всех $h$. (Указание: использовать теорему 16.)


Up: Логические формулы и схемы Previous: 2. Полные системы связок Contents:


Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования