Нижние оценки сложности вычисления булевых функций тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

$ 3 , 9'1

АКАДЕМИЯ НАУК СССР ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ МАТЕМАТИЧЕСКИЙ ИНСТИТУТ ИМЕНИ В. А. СТЕКЛОВА

На правах рукописи УДК 519. Я5

РАЗБОРОВ Александр Александрович НИЖНИЕ ОЦЕНКИ СЛОЖНОСТИ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ФУНКЦИИ 01.01.06 - математическая логика, алгебра и ¡•еория чисел

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1990

с

о

! .

Работа выполнена в Математическом Институте АН

В. А. Стеклова

Официальные оппоненты: доктор физико-математических наук Андреев А. Е. доктор физико-математических наук КарацуОа А. А. доктор физико-математических наук Слисенко А. П.

Ведущая организация мс/шшкс»-1игематнчшжпй фик/дь-.с".

М. В. Ломоносова

заседании специализированного совета Д. 002.38. Математическом Институте АН СССР им. В. А. Стеклова пс Москва, ул. Вавилова, 42.

С диссертацией можно ознакомиться в библиотеке Матема Института АН СССР им. В. А. Стеклова

Защита состоится

1991 г. в

Автореферат разослан

Ученый секретарь специализированного совета кандидат физико-математических наук

В. I

-э-

Общая характеристика

Оценивание сложности вычисления (реализации) явно заданных булевых функций с помощью различных дискретных вычислительных устройств (таких как, например, схемы из функциональных элементов, контактные схемы, ветвящиеся программы и.т.д.) составляет предмет теории булевой сложности. Первые пионерские работы, посвященные этому вопросу, появились еще в 30-х годах (см., например, [5]). Ряд ярких результатов в теории булевой сложности был доказан в нашей стране в 60-е годи. К ним можно отнести, например, работы Л.А.Маркова. 5. А. СуоботовскоП. Э. И. Нечипорука, В. М. Храпченко [1,3.2.4! £? последующие годы наблюдался некоторый спад активности в этой области.

Интерес к рассматриваемому предмету снова возродился в начале 80-х годов в связи с нуждами теории вычислительной (тьюринговой) сложности, и особенно в связи с запросами теории ■ полиномиальной вычислимости. Именно, оказалось, что сложность распознавания данного языка £ машинами Тьюринга самым тесным образом связана со сложностью вычисления ассоциированной с г последовательности булевых функций. На самом деле для всех наиболее часто рассматриваемых в литературе мер тьюринговой сложности (время, объем памяти, сложность в параллельных вычислениях, число альтераций и. т. д.) существует соответствующая булева модель. При этом булевы модели устроены проще и нагляднее, чем соответствующие тьюринговы модели. Кроме того, они сильнее последних, поэтому нижние оценки для булевых вычислений влекут аналогичные оценки для тьюринговых вычислений. Все эти обстоятельства и обусловили возрождение интереса к получению оценок (особенно нижних!) сложности вычисления явно заданных булевых функций.

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

Главной целью диссертационной работы -является

получение таких оценок для некоторых более слабых вычислите.; моделей. К этим моделям относятся монотоннио схемы, с ограниченной глубины в базисе {-чл.у, ®| и контактно-венти.) схемы.

Общим для этих результатов является то. что в их ос лежит один и тот же метод, получивший в литературе наз! лея ода аппроксимаций. Для наиболее интересного случая - с.) функциональных схем общего вида, этот метод формализуется тг легко, как и для трех приведенных выше. Следовательно, (. поставить вопрос о границах применимости данного метода к с> общего вида. Некоторые результаты в этом направлении 1 включены в диссертацию.

Результаты диссертации являются новыми и г, теоретический характер. Они докладывались на Междунэрс Математическом-Конгрессе (Беркли. 1986), 8 и 10 Всесок конференциях по математической логике (Москва,.. 1986 и Алма-1990), ряде зарубежных конференций. Кроме того, докладывались на Общеинстигутском семинаре МИАН СССР, Москов Математическом Обществе, семинарах кафедр математической ло и дискретной математики механико-математического факультета в ряде зарубежных научных центров.

Результаты диссертации опубликованы в работах [6-10].

Содерхание работы

Диссертация состоит из введения и 6 глав, разбитых н; параграфов. Общий объем -диссертации - 106 страниц. Сп литературы содержит 64 наименования. Нумерация утвержд отражает их расположение относительно глав. Исключ составляют теоремы, служащие основными результатами диссерта: для которых принята однозначная нумерация.

В главе 1 вводятся необходимые определения и формулиру; основные результаты диссертации.

В §1 главы 1 приводится уточнение интуитивного пои: "явно заданная последовательность булевых функций" определяются некоторые важные функции, использу* в-дальнейшем.

Множество (o,i)n всех двоичных слов длины п будет называться

л-лерныл булевыл кубол и обозначаться через в". Булев куб в" может быть естественным образом отождествлен с семейством всех подмножеств Я([л]> стандартного л-элементного множества [л] « (1,2,...,п). При этой отождествлении множеству двоичных слов, содержащих ровно s единиц (s-a слой булева ■ куба)

соответствует семейство (л)5. состоящее, по определению, из всех s-элементных пвдмножеств множества [п]. Для двоичного слова и е

вп через и<п обозначается i-я компонента этого слова. В тех случаях, когда это не может вызвать недоразумений, мы сокращаем

</" до и'.

Булевой функцией от п переменных называется произвольной

отображение í вида f-.в" —» (о,ц. Множество всех булевых функций от п переменных будет обозначаться через гп. а всех

монотонных булевых функций из Fn - через . При рассмотрении

функций из Fn элемента булева куба в" иногда называют (булевыми) , вхоОаяии Для множества булевых входов и утверждение Va € с (fia) - с) (где с € {0,1}) будет записываться в сокращенной форма t(U) - с.

Последовательность булевых функций (fn), где fn - функция от

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

Пример 1.4. п-конъюнкция лв и п-диэъхмкция vn - это

следующие булевы функции от п переменных: лп г г$л ...л *n; vn =

XV —V х . I п

Пример 1.5. Булева функция nook п е гп сложения по mod л определяется следующим образом:

MODH п(а) » г s U<1)+ ...4 вс«> ж О (eod к). Функция mod, „ сложения по nod г также обозначается через »"Г

¿ gil п

Пример 1.6. Функции слоя £k п и пороговые функции тк определяются следующим образом:

Eu. „(«) - 1 - и<0+ и<п) « к,

К fit

Тк пЫ - 1 * а(,)+ ...+ н<п) г

Функция т\п/2\ п называется функцией голосования и обозначается через члзп.

Пример 1.7. Рассмотрим следующую алгоритмическую задачу КЛИКА:

УСЛОВИЕ. Задан неориентированный граф g = и

натуральное число s.

ВОПРОС. Содержит ли с полный подграф i "клику"> с s вершинами?

Следующая монотонная Оулева функция cliquer,s) от л =

переменных <xtJ | 'i.s i < j s ■} кодирует индивидуальные

входы {y,e,s) задачи КЛИКА, для ко тори* |к| -

cmqvein,*) я V Л

ГС[Я] i,j€V 13 | V | ms i<j

Пример 1.8. Рассмотрим алгоритмическую задачу СОВЕРШЕННОЕ ПАРОСОЧЕТАНИЕ В ДВУДОЛЬНОМ ГРАФЕ (известную также под названием БУЛЕВ ПЕРМАНЕНТ):

УСЛОВИЕ Дан двудольный гра$_о - (p,q,e) ; |р| - |о| - и,-

Е с PxQ.

ВОПРОС. Содержит ли с совершенное паросочетание? Соответствующая монотонная булева функция илтсн (га) от m2 переменных {jr1J | i s i s j s и> задается соотношением

НЛТСЩа) s V Л <D

<resm jetmj 1<г(1>

(альтернативное название "БУЛЕВ ПЕРМАНЕНТ" объясняется сходством формулы (1) с формулой для перманента).- - - —

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

некоторых обозначений. используемым в диссертации для соответствующих мер сложности.

Cg(f) - сложность реализации функции f функциональными

схемами в Оазисе Б.

c(f) - сложность реализации функции t функциональными схемами в Оазисе (л,v), на входы которых подаются как переменные так и их отрицания (известно. что с точностью до мультипликативйой константы эта мера сложности эквивалентна Cg{f) для любого конечного полного базиса Б). Такие схемы называются схелаш общего вида.

Через cf(f> обозначается с( f V|C> (.'оотпетсгнуншис -'опы называются монолитными

Cg(f) - сложность реализации функции t функциональнши схемами глубины s d в Оазисе Б.

- * ci(f), где Б - <•. л , v , cn € W)

О п п п

- с^ . где Бк - {-.п, лп, v„. коок п (п € N)) (к фиксировано).

Rs(f) - сложность реализации функции f контактно-вентильными схемами.

§2 завершается обсуждением взаимосвязей между дискретными (булевыми) и тьюринговыми вычислительными устройствами.

В §3 главы 1 формулируются основные результаты диссертации. При этом удобно использовать следующие обозначения. Если g и л -две функции одних и тег- же аргументов (в роли которых могут выступать натуральные числа, булевы функции и.т. д.). принимающие

значения в R+, то запись g г П(Л). по определению, означает, что существует такая константа оо. что при любых значениях аргументов выполнено соотношение g 2 ch. Аналогично понимаются и

более сложные выражения: например, c5(fn) 2 nn(logn) означает

Зс > о Vn е Н cE(fn) г nclogn (основание логарифма при этом, как

легко видеть, несущественной g • e(h) означает коныонкцию двух утверждений: g 2 п(й) и h г ti(g). Запись g 2 u(/i) определяется лишь для случая, когда g и h - функции одного натурального аргумента п и означает, что

?(П)

lim jjjpjT- = со. Легко видеть, что g i. n(ii) « h s o(g) и i

П-kn ' '

u(/i) в h s o(g).

К основным результатам диссертации относятся с. нижние оценки.

(log и)-0(1)'

ТЕОРЕМА 1 (нижние оценки монотонной сложности КЛИКА).

а

с+|сх101/г(т, г) | г

СЛЕДСТВИЕ 1 (сверхполиномиальные нижние оценки, дос на основании теоремы 1). Если П(1одт) < в(т) < т-тП(1', я

с;-[Ьидо£{тГ«<»)>] г тП(1одт).

СЛЕДСТВИЕ 2 (случай малых клик). Если я(т) <. о{ 1). ио

СГ+|ст.10иЕ(га,5(и)) | г п

log"m

ТЕОРЕМА 2 (сверхполиномиальные нижние оценки мон СЛОЖНОСТИ функции СОВЕРШЕННОЕ ПАРОСОЧЕТАНИЕ В ДВУДОЛЬНОМ

с+(ядгсн(ш)] г тП<1о*тК

ТЕОРЕМА 3 (экспоненциальные нижние оценки си реализации функции голосования схемами ограниченной глу базисе (-1,л,у,в>).

С*(|Шп) * exp|fl(n1/'ad~1) J.

Обозначим через t(x,y) "функцию бати' двух нату] аргументов г и у, определяемую следующей рекурсией:

t(0,y) s у,

t(x+l,y) = 2t(x'yi Положим 1од*л Й шах (г | t(jr.l) s n).

ТЕОРШЛ 4 (сверхдинэйная нижняя оценка сложности реализации различных симметрических функций контактно-вентильными схемами). Пусть н обозначает любую из трех функций иос, е, т (сл. примеры

1.5, 1.6). Тогда ^(Нк п) г п|(п-К) •1од1одп1п(Л.1од*п)|. В

часжносжи, RS(HAJn) г С1(л • logloglog*n).

СЛЕДСТВИЕ. Пусть к(п) s п-и

- произвольная

logloglog n

функция и и - любая из трех булевых функций e.t.hod. rs("h(n) n) линейка по п тогда и только тогда, когда k(n) < o(i).

В главе 2 делается первый шаг в направлении доказательства теорем 1-4. Именно, показывается принципиальная возможность сведения проблемы получения нижних оценок сложности"вычисления булевых функций к оцениванию некоторой величины, носящей чисто комбинаторный и "статический" характер. Именно эта редукция лежит в основе метода аппроксимаций.

В §1 главы 2 рассматриваются монотонные схемы и схемы общего вида, причем изложение ведется параллельно для обоих случаев. Монотонной правильной моделью с п переменными называется произвольная тройка <го,л,v>, где

<о, 1. xt (isis»))iiis rn, (2)

а л и v - две бинарные операции на т. Определение правильной модели с п переменным, дается так же, как и определение монотонной правильной модели с той единственной разницей, что (2) усиливается до

{О, 1, Ij (1 s i s 11, с 6 (0,1))) с » С гл. (3)

Для g,E е зп;* е {a,vj положим

«¡(д.Н) *

где \ - булева функция от двух переменных, заданная соотношением х\у ^ хл{->у). Положим, далее.

A* s I д.Ъ € т.- . 6 (л,у|): л" - (i~(çr.H) I g.H 6 я,- , 6 (A,V)I. Для г с Fn. 7е» расстояниел p(f. 7) лехду fut назовем наименьшее натуральное t. для которого существуют г*.....a J е

4* и Jj, .., е такие, что:

^ t { s f V V а*, i « i 1

t.

f i f v V 4" v i i - j

сюлижнм. HUKflliliU (M / 111) rain pi f.f) ^ЛВДУЬРШЯЯ '.!•"!>(!!'"

Г его

является основным результатом 41 главы 2: ,

ТЕОРЕМА 2.1 а) если m монотонная правильная модель с п переленными и f € ко

C+(f) г р(Г.Я);

б) ecjii го - правильная лодель с п переменными и f е F . ио с(/> г p(f.W).

В $2 главы 2 устанавливаеся аналогичная редукция для схем с ограничениями на глубину.

В 53 главы 2 рассматриваются контактно-вентильные схемы. Зафиксируем два произвольных непересекающихся множества булевых

входов v я v. Обозначим через j семейство всех монотонных1' функционалов f:?(U) —♦ {o.i>. не равных тождественно константе.

Введем сокращение i/: s t/nx^. Для isisn, с € (о. i). л ç и полагаем

6i с(Л) ' е **r I rí " с. г(л) = тг гглпир-^ oj.

PfU) считается упорщоченныы по включению.

-и-

Дусть, далее,

л = {«^СМ> | 1 5 1 5 п. с е (0.1), л с (4)

Мы говорим оО элементах множества как о яочках, а об элементах множества д - как о покрывающие лножвежвах. Обозначим через т (I/. V) наименьшее число множеств, покрывавших все точки из Следующая теорема является основным результатом §3:

ТЕОРЕМА 5. Пусяъ и.у с в": V о V - я. Тогда т(У, к) -

лип|/?5(Л | Г € Гп. Г (и) <= О, Г (К) =

В этом параграфе она доказывается в сторону "<", доказательство в другую сторону откладывается до §3 главы 6.

Глава 3 посвящена доказательству теорем 1и.2. г В §1 главы 3 показывается, как по всякому семейству конъюнкций в от л переменных, обладающему свойством

1,* (1 & I * П) € и

и натуральному числу г г г построить некоторую монотонную правильную модель я. Кроме того, в этом параграфе устанавливается следующий простой общий результат, указывающий на возможность применения вероятностных методов для получения нижних оценок на величину <>(/, я>:

ЛЕША 3.1. Кля любой-лонолонной правильной людели я, функции

{ € *п°П и паРы вероятностных распределений и.у на в"

справедлива оценка

Р[Г(у) - 1]-Р[7(У) - 1]

р{Г,Я1) 2 в1п шах

?езп

а*

Р[7(и)1]-Р(Г(ц) - 11__

<1"

где <}* и сГ задатся сиедцкщиси формулами:

(¡' - аах Р[5+ (V) « 1), (5)

« еД

а' а в«х Р(г"(ц> - 1]. (6)

В 52,3 главы 3 выбираются подходящие пары (п.г). строятся соответствупвие монотонные правильные модели и на основании лемлы 3. 1 оцениваются расстояния от функций КЛИКА (в §2) и СОВЕРШЕННОЕ ПАРОСОЧЕТАНИЕ В ДВУДОЛЬНО« ГРАФЕ (§3) до этих моделей. После этого доказательства теорем 1,2 завершаются применением теоремы 2.1 а).

В 64 главы 3 приводится обзор результатов других авторов и результатов самого диссертанта, не включенных в диссертацию, имеющих отношение к материалу главы 3.

В главе 4 завершается доказательство теоремы 3.

В §1 этой главы устанавливается простой результат, аналогичный лекме 3.1 и с его помощью доказывается, что всякая булева функция, вычислимая схемой ограниченной глубины и "небольшого" размера в базисе (->,л,у,»), хорошо аппроксимируется полиномами "малой" степени над г2. В 52 на основе этой редукции завершается доказательство теоремы 3. В §3 приводится краткий обзор других результатов, имеющих отношение к материалу настоящей главы.

В главе 5 завершается доказательство теоремы 4. На самом деле доказывается более сильное утверждение - при определенных ограничениях на » и а любая булева функция, отделяющая два слоя

тз—- и [п]5 булева куба я". имеет нелинейную сложность реализации контактно-вентильными схемами.

В 61 главы 5 среди совершенно необозримого множества точек гхг (см. выше) выделяется некоторое разумное подмножество. Далее формулируется лекма 5.1, утверждающая, что даже для покрытия этого подмножества требуется нелинейное число покрывающих множеств. Теорема 4 при этом непосредственно следует из теоремы 5 и этой леммы.

§2 главы 5 целиком посвящен доказательству леммы 5.1.

В §3 содержится краткий-обзор результатов, предшествовавших

появлению теоремы 4.

Заключительная глава 6 стоит несколько особняком. В ней в-основном исследуется вопрос о возможном поведении величины где ш - произвольная правильная модель. При этом оказывается, что ответ на этот вопрос существенно зависит от ' того, допускаются ли вспомогательные переменные или нет.

В §1 приводятся точные ¿формулировки доказываемых в главе 6 результатов. При этом по причинам, которые станут понятны чуть ниже, удобно слегка обобщить рассмотренную в §1 главы 2 ситуацию н предположить, что функция { е гп существенно зависит лишь от первых пц переменных (п < п), а в определении правильной модели

ослабить (3) до (о. 1. х\ (1 < 1 &по), с е {0,1>} с -т.

Доказательство теоремы 2.1 0) обобщается на рассматриваемый случай. Разумеется,- при.по = п получается определение правильной модели в смысле главы 2. ■

ТЕОРЕМА 6. Для произвольной булевой функции с е г ,

существенно заЬиащей ох по (ло * п) переменных и произвольной

правильной модели го справедливо неравенство р(е,Щ $ о(поп).

В частности, при ло = п получаем р(л 5Л) ^ о(п2). Следующая теорема показывает, что ситуация, возникающая при попытке использовать очевидный аналог леммы 3.1 для оценки снизу расстояния р(г.ш), еще хуже, чем с теоремой 2.1 б):

ТЕОРЕМА 7. ¿ля любой булевой функции г е гп. существенно

зависящей от по {по 5 п) переменных, любой правильной модели ш и

любой пары распределений и,* на в" справедлива оценка

1Р = 1]-р[? (V) = 1] р[?(и) = 1]-р[г(а) = x 1

Ш.П

7ет

а*

О(по). где <1* и <Г задаются формулами (5), (6) соответственно.

Теорема 6 в принципе не исключает возможности доказательства сверхполиномиальных нижних оценок для с(/>, где f(x1, х ) - функция от л переменных, путем введения большого числа

о

вспомогательных переменных *п 41» хп +2.....хп с пос-л.едающей

о о - - *

оценкой расстояния р(г.го) для подходящей правильной модели т с г . В §1 далее явно описываются правильные модели некоторого

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

о

правильную модель такую, что С(Г) <: °[р(^.я,гаах)+п]3

(теорема 8).

Последняя теорема главы 6 устанавливает оценку, аналогичную оценке теоремы 7 для случая контактно-вентильных схем:

ТЕОРЕМА 9. Кхя любых и.у с в"; и П v = в на множестве й,

определенном формулой (4), существует, такое распределение з. что

Оля любой точки (Г,г) е р[(г,у) е 5] > П(1/п).

Теорема 9, в частности, дает объяснение тому факту, что в §2 главы 5 требуется привлечение более сложной - комбинаторной техники, нежели прямой вероятностный метод. ■ использованный в главах 3,4.

В §2 главы 6 доказываются теоремы 6.7 и 9. Основной компонентой в их доказательствах является следующая лемма:

ЛЕММА 6. 1. Для произвольной булевой функции г б г ,

существенно зависящей оя ло (по 5 п) переменных и произвольной

правильной модели ш существуют такие распределения 7 на ш. а* на

и в" на л", что для любого г е г"1(г) выполнено

Р[?(Г) - о] 5 О^По-Р[в*(Г) = 1]|

у, аналогично, для любого и е г'г(о)

р[?(и) = 1] 5 о|по-Р[«'(и) = 1]|.

В §3 доказывается оставшаяся часть теоремы 5 и теорема 8. §4 главы 6 посвящен аналогичным общим результатам, доказанным относительно двух других методов для получения сверхполиномиальных нижних оценок монотонной формульной сложности, упоминавшихся в §4 главы 3. _

Я приношу свою искреннюю., благодарность, С. И._Адяну за создание на протяжении всех этих лет условий, максимально

плнгоприятствуюших плодотворной научной работе.

Литература

1. Марков А. А. "О минимальных контактно-вентильных двухполюсниках для монотонных симметрических функций" - В кн.• "Проблемы кибернетики", вып. 8. М.. 1962. с. 117-121.

2. Нечипорук Э. И. "Об одной булевской функции" - ЛАН СССР. 1966. т. 169. №4, с. 765-766.

3. Субботовская Б. А.~ "О реализации линейных функций формулами I! оазнсо ( v, 4, - ) " - ДАН СССР. 1963, т. 149, №4, с. 784-787.

1. Храпченко В. M "О сложности реализации линейной ф.ункшш !.< классе п-схем" Молем. зам., 1971, т. 9, вып. 1, с. ЗЬ-40.

Ь. Shannon С. "A symbolic analysis of relay and switching circuits" - Transactions of American Inst. of Electrical Engjne-ers, V. 57, 1938, p.713-723.

Работы автора по теме диссертации

6. Разборов А. А. "Нижние оценки монотонной сложное?:; некоторых булевых функций" - ЛАН СССР, 1985, т. 281, tM. с. 798-801.

7. Разборов А. А. "Нижние оценки монотонной сложности логического перманента" - Мажем, зам., 1985, т. 37, вып. С,

с. 887-900.

8. Разборов А.А. "Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения" - Метел, зал., 1987, т. 41, вып. 4, с. 598-607.

9. Razborov д.A. "On the raethod of approximations" - Proc. of 21st ACM STOC, 1989, pp. 167-176.

10. Разборов A. A. "Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами". "Математические залети', 1990, т. 48, вып. 6, с. 79-91.