О сложности булевых матриц тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

московский государственный университет р Г 5 0 д давни м.в.ломогосова

МЕШИКО-МАТШТИЧЕШИ ФАКУЛЬТЕТ

На правах рукописи УДК 519.7

Чашкин Александр Викторович О СЛОЖНОСТИ БУЛЕВЫХ МАТРИЦ

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

москва - 1994

Работа выполнена на кафедре дискретной математики механико-математического факультета МГУ им. К.Е.Ломоносова

Научный руководитель - член-корреспондент РАК, профессор О.Б.Лупанов.

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

кандидат физико-математических наук Г.А.Ткачев.

Ведущая организация - Институт математики Сибирского отделения РАН.

' 9

I "М "

Защита диссертации состоится "-О "ЦЛаЛЬ^ЬхУ 1994г. в 16 час. 05 мин. на заседании диссертационного совета Д.053.05.05. при МГУ по адресу: 119899, ГСП, Москва, Воробьевы горы, МГУ, механико-математичссийй факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ .-(14,этак)-. - . .

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

Ученый секретарь диссертационного совета Д.053.05.05. при МГУ доктор физико-математических наук, профессор

В.Н.Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

...... Акт^альяость_теш:-.Одкой из-основных-задач даскретноЗ математики -

и математической .кибернетики является задача изученая сложности порождения различных комбинаторных объектов: булевых функций, чисел, последовательностей целых чисол и т.д., исходя ' из некоторого начального запаса элементарных объектов в соответствии с определенными правилами. Под сложностью порождениякак правило, понимается число шагов, за которое исследуемый объект может быть порожден. Е диссертации исследуется именно такая задача: задача о сложности порождения булевых матриц схемами из функциональных элементов. Матрицы при этом порождаются схемами, исходя из множества начальных объектов,' позываемых в дальнейшем генераторами. В качестве генераторов использованы либо булевы векторы, либо булевы матрицы. 'Схемы, порождающие матрицы, исходя из генераторов-векторов, состоят из функциональных элементов, выполняющих- покомпонентные булевы операции над булевыми векторами, а схемы, порокдакцие матрицы, гсходя из-.генераторов-матриц,, состоят из-функциональных элементов, выполняющих покомпонентные булевы операции над булевыми аатрицами. В первом случае будем говорить о У-порокдении матриц, а во втором - о м-порождешш матриц схемами из функциональных элементов..

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

результаты о сложности . порождения графов, так как любая матрица является матрицей смежности некоторого графа (двудольного графа). А графа" объекты "не- 'менее- распространенные ■?.■ математике чем матрицы. Наконец матрицы можно рассматривать как частичные булевы функции-(при М—порождении) и системы частичных булевых функций' (при У-поровдении). '

Цель работы. I)Исследование сложности V- и и-порождения матриц, исходя из некоторых специальных множеств генераторов, и сравнение этих сложностей со сложностью вычисления ' соответствующих булевых функций схемами в полных .базисах. Соответствие между булевыми функциями и булевыми матрицами устанавливается естественным образом, так как любая булева функция может быть задана двумерной таблицей своих значений, т.е. матрицей,, а любая булева матрица может рассматриваться как двумерная таблица значений некоторой булевой функции/ 2) Изучение поведения функций Шеннона пороадения булевых матриц.

• • В работе используются метода дискретной

математики и математической кибернетики.'

Научная новизна. Все основные результаты диссертации являются новыми. В диссертации найдены асимптотически точные формулы для функций Шеннона ы-порождения булевых матриц размера шт схемами в базисе, состояаем из не' более -чем г-местных операций дизъюнкции и крнъшкции, при достаточно слабых ограничениях,. накладываемых на величины п,т н г (аналогичные результаты для У-поровдения могут быть легко' получены при помощи конструкций, использованных в случае' М-порокдения). В случае г=2 и п<1о^т найдены точные значения этой

функции. Для у-порозвдения матриц схемами в нескольких различных 5ээисах при также найдены точные значения фушсции Шеннона.

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

Диссертация носит

теоретический характер. Результаты, полученные в диссертации,' могут найти применение в теории сложности алгоритмов и вычислений, а также при создании программного и аппаратного обеспечения вычислительной техники. - ■ ""

Апробация работы. Основные результаты диссертации докладывались на научных семинарах в МГУ им. М.В. Ломоносова.

Публикашк. Основные результаты диссертации опубликованы.

Структура и объем работы. Диссертация состоит из введения, двух глав и списка литературы, включающего 17 названий. Объем работы 67 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении формулируются цели работы, кратко излагается содержание' диссертации и приводятся основные определения."

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

Пусть .* - Некоторая бинарная булева операция, а w,u,v - булевы матрицы, размера пхт. Будем говорить, что матрицы связаны

соотношением w=u*v, если при всех i<i<n и всех 1<д<т выполняется равенство н..=ц..*v... В этом случае будем тага® говорить, что

Xj XJ 1J

матрица w является результатом покошонентного действия операции * на..матрицы, и и V.. ..

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

Гак как любой вектор длины m можно рассматривать как матрицу размера 1хт, то также определено и действие произвольной булевой операции * на булевы векторы длины т.

Пусть Б - некоторое множество булевых операций, Б' --множество функциональных элементов, выполнявдих. операции из Б на булевых векторах длины т, а с - некоторое-множество булевых векторов той же

ДЛИНЫ•

■Схему S' назовем V(B,G' Ьсхемой, если S' состоит из функциональных элементов, принадлежащих множеству Б', а на входные полюсы S' подаются элементы множества G'.

Пусть, далее, Б" - множество функциональных элементов, выполняющих операции из Б на булевых матрицах размера nxm, - а G" -некоторое множество булевых матриц того же размера.

Схему S" назовем м (Б, G") -схемой, если S" состоит из функциональных элементов, принадлежащих множеству Б", а на входные

полюсы С" подаются элементы множества а". Для ?(Б,С')- и М(Б,С")-схом множество Б назовем базисом схемы, а множество вектороБ С'--и к1Ю".пство матриц а"- - множествами--генераторов соответствующих схем.

Пусть и,-г - вершины схемы 5. Вершину и назовем, потомком вершины у, а горпмну V - предком вершины и, если -и и V связаны ребром, ориентированным от у к и.

Определим для какдой вершины и схемы в матрицу (в.ехтор) потюждаемуя в этой вершине. Это-делается индуктивно, в соответствии с естественным частичным упорядочиванием вершин схемы Б. Пусть я -М(Б,С) СУ(3,С))-схема. Если я - входной, полюс Б, к которому присоединен генератор с, то положим Если вершина иг схемы Б

является потомком вестин и,у, и в вершине « выполняется операция *, то полагаем

Будем говорить, что У(Е,с)-схема э порождает булеву матрицу размера п*т, если в в найдутся п вершин ^ таких, что з(и^) совпадает с 1-ой строкой матрицы V? при 1<1<п.

• • Будем-говорить,"что -М(Б,0-схема-з-порождает булеву матрицу размера п*т, если в Б найдется вершина и такая, что Б(и)=я.

Слохностью схемы 5, как обычно, назовем число функциональных элементов, содержащихся в Б.

Число с(я) назовем 7Б с-сложностью матрицы те, если оно равно сложности минимальной у(Б,0-схемы, порождающей матрицу иг.

Число мБ назовем кБ с-слокностью матрицы и, если оно равно сложности минимальной м(Б,с)-схемы, порождающей матрицу Ч.

М(Б,с)-схему 5 назовем Р(Б,й)-формулой, если выход каждого

элемента схемы, исключая элемент, являющийся единственным выходным полюсом Б, присоединен ко входу ровно одного элемента схемы. - ■ Число- с назовем г^ ^-сложностью матрицы •?>,'■ или просто ' формульной сложностью, если оно равно сложности минимальной РБ ^-формулы, порождающей матрицу и.

Основное внимание в диссертации уделено случ&ю, когда множество генераторов в состоит из всех векторов, содержащих ровно одну ненулевую компоненту. В этом случае, говоря о ^ с-слокности матрицы ш, будем опускать 'символ б и обозначать эту сложность через Аналогично поступим, рассматривая ¡^ 0-сложность матрицы я, если б .состоит из всех матриц, имеющих ровно одну ненулевую линию (строку или сВлбец), состоящую сплошь из единиц. Такую сложность обозначим через В первой главе в 'качестве базиса Б использованы

следуювде множества: Б. - множество всех не более чем двуместных "" "булевых операций, Б2 - множество всех 'не более чем" двуместных булевых операций, сохраняющих ноль, Как вспомогательное

•' средство при-доказательстве некоторых* утверждений использован базис Бд, состоящий из единственной операции V. Во второй главе в качестве базиса Б использована' множества Б , состоящие из ке более чем г-местных операций дпзыонкции и конъюнкции. Заметим, что множество Б2 второй главы совпадает с множеством Б^ первой главы.

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

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

первой последовательности одинакова для" всех рассматриваемых базисов и равна примерно Зт, а сложность порождения матриц из второй - последовательности- существенно -зависит- от- базиса -и принимает • значения от примерно m до Зт.

Во втором параграфе первой главы исследуется функция Шеннона v-порокдения узких булевых матриц.

Функцию Шеннона Vg(n,m), определим равенством

VR(n,m)=max Vr,(W), to д о

где максимум берется по всем булевым матрицам размера пхш.

Для функции Шеннона Vg(n,m) найдены точные значения, при услов1Ш n<log0m, (теорема 1), и асимптотически точная формула - при условна log2m<rK(2--»E )log2m, где последовательность ещ удовлетворяет условиям: 0<ет<1, е icggm-«» при nw<» (теорема 2).

В третьем, пятом и шестом параграфах_диссертации изучается, связь между сложностью порождения, матриц и сложностью вычисления соответствующих . этим матрицам булевых функций. Подобный вопрос изучался ранее Пудлаком, Редлем и Савицки в В этой статье рассматривались двудольные графи, дола которых содержат по ^ вершин. •В для таких-графов было установлено, что-получение нижней оценки _сложности порождения в базисе Б^, больней чем araiog0m, где a -какая-нибудь" постоянная, большая единицы, равносильно получению экспоненциальной нюней сценки сложности для булевых функций при их вычислении схемами в полных базисах.1 Теоремы, приведенные в _

^ Pudlak P., Rodl Т., Saviclqr P. Graph complexity. Acta Intormatica 25, 515-535 (1983).

рассматриваемых параграфах этот результат значительно усиливают. Точнее, для булевых матриц размера г.хт показано следующее (теорема 3). .При .растуЕЭм т ■к ':п=0(хо|мп] • ^"У40-159 ■ сравнительно .невысокой .

нижней оценки сложности вида (»?)>( 2+е)ш для какой-либо

положительной постоянной е, даже в таком базисе как-Бд, равносильно

установлению нелинейной нижней оцени! сложности для' булевых функций.

Получение такой ке оценки у^-сложности при выполнении более сильного 1 -Л

условия: п<ш где 6 - постоянная, 0<б<1, равносильно уже установлению экспоненциальной низшей оценки сложности для булевых функций. Аналогичным образом для К^-сложности (теорема б) показано, что установление нижней оценки вида М^(тг) > (2+£)(ш+п), где е -положительная постоянная, также равносильно установлению экспоненциальной нижней оценки сложности булевых функций. Похожие результаты (теоремы 7,8) доказаны и для МБ ^сложности

симметрических матриц при их порождении, исходя' из специального

множества генераторов 2. Симметрические матрицы представляют особый

интерес,-так как являются матрицами смежности графов, а генераторы

из множества Ъ соответствуют звездам вершин.

Кроме этого в пятом параграфе приведена последовательность -

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

2(п+т),и для этой сложности найдено точное значение.

В четворто!.: параграфе первой главы исследуется функция Шеннона

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

Функцию Шеннона Кг, (п',т), определим павенством а3

(п,тп)=тах Нс (¥/), •°3 V? ь3

где максимум берется по всем булевым матрицам размера пхт.

Для функции Шеннона мс (n,m) найдены точные значения, при

3

условии n<log2ra (теорема 4) ^ и асимптотически точная формула' - при условии iog2m<n<(2-£m)log2m, где последовательность ея удовлетворяет условиям: о<£ <1, snlog0m-.vo при т-со (теорема 5).

Во второй главе диссертации исследуется асимптотическое поведение функции Шеннона к-порождения булевых "Матриц, в том числе и симметрических, схемами и формулами в базисах При достаточно слабых ограничениях, намалываемых на размеры матриц и величину г, установлены асимптотически точные формулы соответствующих функций Шеннона (теоремы 9-13). Ранее были известны порядки роста

функции Ианнона порождения ..симметрических матриц схемами и формулами в базисе Б„, а также асимптотически точные формула Функции Шеннона реализации булеЕых матриц вентильными схемами ". rie трудно убедиться, что задача о сложности реализации булевых матриц вентильными схемами .во многом сходна. с задачей порождения булевых

?)

' Pudlak Р., Redi V., Savicky P. Graph complexity. Лога Informatics 25, 515-535 (1988).

Bublitz, S. Decomposition oí graphs and monotone formula sise oí homogeneous functions. Acta Informatics 23, 639-¿9b (1936).

ч' !Pu2a, Z. Covering of graphs by complete bipartite subgraphs, aomplexity of.0-1 matrices. Combinatorics 4, 111-116 (1984).

^ Лупанов О.Б. 0 вентильных и контактно-вентильных схемах. - Докл. АН СССР. -1956. - Т.З," - С. 1171-1174-

матриц схемами в базисе, состоящем из одной дизъюнкции.

Автор глубоко благодарен профессору О.В.Лупакову за постоянное вниматге к работе.

Основные результаты диссертации опубликованы в работе: Чашкин A.B. О сложности булевых матриц, графов и соответствукшх им булевых функций,- Дискретная математика, 1994, 6, 43-73.

\