ДОКЛАДЫ АКАДЕМИИ НАУК, 2012, том 447, № 6, с. 607-609
МАТЕМАТИКА
УДК 519.714
СРАВНИТЕЛЬНЫМ АНАЛИЗ СЛОЖНОСТИ БУЛЕВЫХ ФУНКЦИЙ С МАЛЫМ ЧИСЛОМ НУЛЕЙ © 2012 г. Ю. В. Максимов
Представлено академиком Ю.И. Журавлевым 24.04.2012 г. Поступило 24.04.2012 г.
В работе исследуется структура минимальных и кратчайших дизъюнктивных нормальных форм (ДНФ) булевых функций, заданных матрицами своих нулевых точек без одинаковых (с точностью до инверсии) столбцов. Известно, что построение ДНФ произвольной булевой функции сводится с линейной сложностью к построению ДНФ функции рассматриваемого типа [1]. Для функций высокой размерности получены рекордные нижние и верхние оценки на минимальное число литералов, содержащихся в реализующих их ДНФ.
Полученные результаты могут быть использованы при реализации и анализе сложности характеристических функций классов в задачах распознавания образов с бинарной информацией [2].
1. Важной частью многих современных алгоритмов машинного обучения для решения задач с бинарной информацией является построение ДНФ булевых функций с малым числом нулей [2, 3].
В подходе, предложенном в работе [2], указанные ДНФ строятся для характеристических функций классов. По полученным ДНФ выписываются оценки близости к классам, по которым производится классификация объектов. Построение дизъюнктивной нормальной формы характеристической функции класса К производится в два шага. На первом шаге строится ДНФ, которая обращается в нуль только на бинарных описаниях объектов из других классов. Затем из полученной ДНФ удаляются те конъюнкции, которые не обращаются в единицу на описаниях эталонных объектов классов К. На основании полученных формул решается вопрос о принадлежности нового объекта к одному из классов.
При синтезе логических алгоритмов классификации число нулей характеристической функции класса (число эталонных объектов), как правило, не велико. Однако в задачах высокой раз-
Московский физико-технический институт (государственный университет), Долгопрудный Московской обл.
мерности прямое построение сокращенной ДНФ по совершенной конъюнктивной нормальной форме (КНФ) невозможно из-за экспоненциального объема необходимых вычислений.
На возможность использования непрямых методов впервые указал С.В. Яблонский. Эта идея была развита в работах Ю.И. Журавлева, А.Ю. Когана, А.Г. Дьяконова и других исследователей [1, 3, 4]. Предложенные ими эффективные алгоритмы позволяют строить достаточно простые ДНФ для различных классов булевых функций с малым числом нулей. Однако вопрос о точных границах сложности ДНФ оставался открытым.
В настоящей работе установлены рекордные верхние и нижние оценки минимального числа литералов в ДНФ реализации булевых функций от большого числа переменных с малым числом нулей.
2. Обозначим Р"к — множество булевых функций от п переменных, имеющих ровно к нулевых точек. Считается, что каждая булева функция /задана своей матрицей нулевых точек Щ, по строкам которой перечислены нули функции.
Булева функция называется приведенной, если матрица ее нулевых точек не содержит столбцы, состоящие только из нулей и единиц, а также столбцы, одинаковые с точностью до инверсии.
Пусть Вк — булев куб размерности к; точки Вк, отличающиеся только в одном разряде, назовем
соседними. Пусть Ф^ — класс приведенных булевых функций из Р"к, не имеющих соседних нулевых точек. Весом булева вектора назовем минимум из числа его единиц и числа нулей. Функции
из Ф^, все столбцы матрицы нулей которых имеют вес не менее X, составляют класс Фпк х .
Обозначим через N множество единиц функции/(хь х2, ..., хп), а через N — множество ее
нулей. Пусть [п]: = {1, 2, ..., п}; — подмат-
рица матрицы М, образованная пересечением строк ¡1,12,..., I,и столбцов]х,]2, ...,]г. Тестом назы-
607
2*
608
МАКСИМОВ
вается матрица с различными строками. Точку а е Bk назовем собственной для ДНФ D функции
f е Р"к, если в D существует ровно одна конъюнкция, покрывающая а. Число литералов, входящих в ДНФ D, назовем рангом и обозначим rank D. Скажем, что почти все функции некоторого класса удовлетворяют заданному свойству, если доля функций указанного класса, для которых оно не выполнено, стремится к нулю при мощности класса, стремящейся к бесконечности.
Во всех рассматриваемых далее асимптотических нотациях ю(-), O(), o(-) предполагается, что n ^ да; то же относится к термину "для почти всех".
3. Метод построения нижних оценок сложности основан на выделении специальных подмножеств булева куба, называемых далее сетями, покрытие которых возможно только с использованием большого числа конъюнкций.
В рамках данного подхода полезным оказывается разбиение множества конъюнкций на непересекающиеся классы, которые определяются присутствием в конъюнкциях заданных комбинаций литералов. Таким образом, задача получения нижних оценок сложности булевых функций сводится к некоторой задаче минимизации, переменными в которой являются мощности классов конъюнкций, а ограничения определяются сетями.
Зафиксируем некоторую приведенную функцию f(xx,
x2, xn) е Pk вместе с ее матрицей нулей M. Обозначим 0(/, j) — точку булева куба, отличную от нуля M[k] функции f только в координате с номером j. Определим множество © (введенное в [5] для доказательства тупиковости некоторых ДНФ) равенством
к k _
© = UU {0( i, j)} \Nf.
i = 1 j = 1
Рассмотрим множество литералов М функции f, которым в матрице нулей Mf соответствуют столбцы с весом [k/3] + 1 и более. Пусть — число конъюнкций, содержащих ровно один собственный литерал из М, К2 — число конъюнкций, содержащих два собственных литерала из М. Остальные конъюнкции объединим в класс К3. В теореме 1 множество © является сетью.
Теорем а 1. Всякая ДНФ приведенной булевой функции f (x1, x2, „., xn) е P"k, не имеющей соседних нулевых точек, содержит не менее 3n(1 + o(1)) ли-
([к/3] + 1 Г ЛЛ
тералов при n = ю! I k .
\ .A t))
х>
Для получения нижних оценок в классе Ф"к х, к!
L3J
+ 1, удобно рассматривать пару сетей ©1 =
= U U {0(i,j)} \Nf и ©0 = u U {0(i,j)} \Nf.
' = 1 j: M = 1 1 = 1 j: Mi = 0
Теорема 2. Минимальное число литералов, входящих в произвольную ДНФ реализацию D функции f класса Фпк х, ограничено снизу выражением
, г. 10 5 к е
rank D > — к--,
3 3(1 + е)
при е = 2-
- X
< 1.
к 4
4. Лучшие известные верхние границы сложности булевых функций устанавливаются редукционным алгоритмом [1]. В частности, при п = = ю(2к/2) редукционный алгоритм гарантирует верхнюю оценку 4п(1 + о(1)) для числа литералов, содержащихся в минимальной ДНФ почти всех
функций из Р"к. В настоящей работе устанавливается верхняя оценка вида 3п(1 + о(1)) для почти всех приведенных функций от достаточно большого числа переменных.
Ненулевой вектор а е Вк назовем разложимым по векторам а1, а2, ..., а,, если а = а1 V а2 V ... V а, и при этом (а, а!) = (а, а2> = ... = (а, а,) = 0, где под символом (а, р) понимается скалярное произведение векторов а и р. Если, кроме того, (а;> ау) = 0 при всех I <у, то вектор а е Вк назовем ортогонально разложимым по векторам а1, а2, ., а,. В случае, когда все координаты вектора а равны единице, набор а1, а2, ., а, назовем ортогональным разложением единицы.
Рассмотрим приведенную функцию /(хь х2, ...
..., хп) е Р"к, заданную матрицей нулей М. Литералу XI сопоставим булев вектор, отвечающий
столбцу к]; литералу Х1 сопоставим его покоординатное отрицание. Выделим в матрице М подматрицу Т с различными строками. Литералы, сопоставленные Т, назовем тестовыми, а сопоставленные М\Т назовем внешними.
Построим гиперграф И1{[(х1, х2, ..., хп)] следующим образом: вершины гиперграфа отождествим с множеством всевозможных литералов функции /;
СТ; СТг СТг
вершины гиперграфа х ^1, х ¡22, ..., х ^ свяжем ребром, если сопоставленные им булевы векторы образуют ортогональное разложение единицы. Ребро, всем вершинам которого, кроме одной, соответствуют тестовые литералы, назовем корневым.
к
к
СРАВНИТЕЛЬНЫЙ АНАЛИЗ СЛОЖНОСТИ БУЛЕВЫХ ФУНКЦИЙ
609
Путем между внешними литералами х;' и х/ в Нт назовем последовательность переходов между внешними литералами внутри ребер гиперграфа,
СТ1
начинающуюся в х1 и заканчивающуюся в .
Рассмотрим гиперграф Бт, полученный удалением из Нт некоторых ребер, а также вершин, не принадлежащих ни одному из ребер. Гиперграф Бт назовем правильным, если всякий внешний
литерал , являющийся вершиной Бт, входит ровно в два ребра, одним из которых является ребро {х;, Х1}; всякая внешняя вершина графа лежит хотя бы в одном пути, начало и конец которого являются корневыми; ребра размера 2 пересекаются только с ребрами размера 3 и более, либо с корневыми.
Теорема 3. Пусть для приведенной функции
/(Х1 , хп} е Рк и теста тсуществует множество правильных гиперграфов {$Те 7, содержащее все внешние литералы. Тогда функция / реализуется ДНФ Б8 , определяемой равенством
= Вт V V V К[ е ],
СТ; ® 1 СТ; ф 1 СТ; ф 1 СТ; СТ;
где К[е] = х^1 х^ ... х^' при е = {х^1, х^, ...
СТ ;
Теорем а 4. Почти все приведенные функции класса Р"к при п > 2к -1 — кС, где С — произвольная
положительная постоянная, может быть реализована ДНФ с числом литералов 3п(1 + о(1)) и числом конъюнкций п(1 + о(1)), при к ^ да. Каждая из полученных границ является асимптотически точной.
В работе [1] рассмотрена так называемая полная булева функция, являющаяся приведенной
2к _1 _ 1
функцией класса Рк , и доказано, что построение ДНФ всякой булевой функции с числом нулей меньшим 1о§2п — 1о§21о§2п + 1 сводится к построению некоторой ДНФ полной функции.
Теорема 5. Полная функция может быть реализована ДНФ, содержащей 3п(1 + о(1)) литералов и п(1 + о(1)) при п ^ да; при этом ни одна из границ асимптотически не улучшаема.
тУ _ 1 _ 1
Из теорем 2 и 5 следует, что в классе Рк существуют функции существенно более сложные, чем полная; тем самым опровергается известная гипотеза о том, что полная функция имеет экстремальную сложность в своем классе.
СПИСОК ЛИТЕРАТУРЫ
1. Журавлев Ю.И, Коган А.Ю. // ДАН. 1985. Т. 285. № 4. С. 795-799.
2. Журавлев Ю.И. // Пробл. кибернетики. 1978. В. 33. С. 5-68.
3. Mubayi D., Turan G., Zhao Y.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.