Экстремальные комплексы граней в единичном кубе

Актуальность работы. Исследования экстремальных комплексов граней в единичном кубе, которым посвящена диссертация, непосредственно связаны с задачей минимизации булевых функций в классе дизъюнктивных нормальных форм (далее ДНФ).

Суть задачи минимизации булевых функций в классе ДНФ состоит в построении формулы вида «дизъюнкция конъюнкций» минимальной сложности для произвольно заданной булевой функции. Эта задача обычно рассматривается в двух эквивалентных моделях — аналитической и геометрической [78]. В аналитической модели используются понятия: булева функция, импликанта, ДНФ, зависящие от п переменных. В геометрической модели эквивалентными понятиями являются подмножество вершин, грань, комплекс граней в п-мерном единичном кубе Вп.

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

Задача минимизации булевых функций может рассматриваться как частный случай задачи синтеза управляющих систем, а именно, как задача синтеза минимальных по сложности формул глубины 2 в базисе {V. &, ->} [45]. Малая глубина ДНФ дает преимущество в надежности и быстродействии перед другими типами схем, но при этом ДНФ существенно проигрывают в схемной сложности. Это обстоятельство способствовало фокусированию исследований на проблемах, которые возникают при рассмотрении минимизации ДНФ как дискретной экстремальной задачи.

Характерной чертой задачи минимизации булевых функций в классе ДНФ является возможность нахождения оптимального решения применением простых локальных операций: уменьшение ранга и удаление импли-кант. Применением этих операций из совершенной ДНФ булевой функции можно получить любую тупиковую, в том числе и минимальную, из произвольной ДНФ можно получить эквивалентную ей тупиковую. Такие преобразования реализуются локальными алгоритмами [23] конечного порядка и их трудоёмкость считается приемлемой.

Задача о поведении максимальных значений числа тупиковых и минимальных ДНФ булевой функции с ростом числа переменных была поставлена С. В. Яблонским в связи с оцениванием трудоемкости алгоритмов минимизации булевых функций.

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

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

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

Большинство задач, которые возникают при минимизации булевых функций в классе ДНФ, относится к полным или трудно решаемым комбинаторным задачам [87, 105]. Поэтому актуальными являются задачи выделения эффективно и неэффективно минимизируемых классов булевых функций, определения достаточных критериев минимальности и обоснованности сокращения перебора в алгоритмах минимизации. Все эти аспекты теории минимизации булевых функций в той или иной мере нашли отражение в данной работе. Таким образом, тема диссертации актуальна как в теоретическом, так и в прикладном отношении.

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

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

Исходными для исследования явились результаты, которые получили следующие авторы: C.B. Яблонский, W. V. Quine, Ю. И. Журавлёв, Ю. Л. Васильев, В. В. Глаголев, A.A. Сапоженко.

Важные результаты по минимизации булевых функций и метрическим задачам в единичном кубе получили также следующие авторы: А. Д. Коршунов, Р. Г. Нигматуллин, Лин Син-Лян, К. Вебер, А. Е. Андреев,

В. К. Леонтьев, О. Coudert, Ю. А. Зуев, Э. Ш. Коспанов, А. В. Косточка, N. Pippenger, Е. Allender, Z. Furedi, J. Kahn, D.J. Kleitman и др.

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

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

Практическая и теоретическая ценность. Работа носит теоретический характер. Вместе с тем, полученные результаты могут применяться для повышения обоснованности и эффективности точных и эвристических алгоритмов минимизации булевых функций: достаточные условия минимальности — для сокращения перебора, методы построения комплексов граней с экстремальными характеристиками — для построения тестовых примеров булевых функций «трудных» для алгоритмов минимизации.

Основными результатами диссертации являются:

1. Доказано существование тупиковых комплексов /с-мерных граней с числом граней порядка 2″ при к < | (1 — е), а при к = о (п) асимптотически равном 2п. Для числа тупиковых комплексов граней получен порядок логарифма равный п-2п. Мощность множества функций, для которых число тупиковых комплексов по порядку логарифма равно п • 2п, сравнима по порядку логарифма с числом всех булевых функций п переменных.

2. Доказано существование ядровых комплексов к-мерных граней с числом граней порядка 2П при к < | (1 — е).

3. Доказано, что число кратчайших комплексов А—мерных граней совпадает по порядку логарифма с числом комплексов, которые состоят из не более 2П1 различных к-мерных граней, при к < § (1 — ?)¦ Для числа кратчайших комплексов граней получен порядок логарифма равный п • 2П.

4. Сформулирован ряд задач минимизации булевых функций для классов мер сложности. Определены специальные классы мер сложности (Ля-, Л/, Ах,)1, которые обладают определенными порядковыми свойствами. Доказаны достаточные условия минимальности комплексов граней.

5. Доказано, что число Л^-минимальных комплексов граней размерности не более к совпадает по порядку логарифма с числом комплексов, которые состоят из не более 2П1 различных граней размерности не более к, при к < | (1 — г). Для числа А^-минимальных комплексов граней получен порядок логарифма равный п • 2П. Мощность множества функций, для которых число А^-минимальных комплексов по порядку логарифма равно п ¦ 2п, сравнима по порядку логарифма с числом всех булевых функций п переменных.

6. Доказано, что максимальное отношение числа тупиковых и минимальных комплексов граней функции по порядку логарифма равно п ¦ 2п для всех мер сложности класса Ап П А/. Максимальное число тупиковых комплексов граней функции может быть по порядку логарифма равно п ¦ 2п и в случае единственного минимального комплекса граней функции для всех мер сложности класса Ап ПАх,. Мощность множества функций с такими соотношениями числа тупиковых и минимальных комплексов (для указанных классов мер сложности) сравнима по порядку логарифма с чис

1 Определение классов мер сложности представлено на стр. 94, 129. лом всех булевых функций п переменных.

7. Доказано существование в единичном кубе Вп монотонного комплекса граней, который имеет тень нижних единиц мощности порядка 2П с константой больше 0.225. Доказано, что почти все вершины из пояса куба, который расположен в средних слоях куба и имеет ширину о (л/п), могут входить в тень нижних единиц монотонного комплекса граней.

Таким образом, для числа граней определенной размерности в тупиковых, ядровых, кратчайших комплексах граней и для мощности тени нижних единиц монотонного комплекса граней доказано, что мощностные верхние оценки достижимы по порядку. Для числа комплексов граней определенного вида (тупиковых, кратчайших, Л^-минимальных) доказана достижимость по порядку логарифма мощностных верхних оценок. При этом верхние оценки максимального числа ДНФ определенного вида для булевой функции считались тривиальными и ставилась задача получения нетривиальных верхних оценок [8, стр. 102].

Апробация работы. Результаты работы были представлены на следующих конференциях: V конференция «Проблемы теоретической кибернетики» (Новосибирск, 1980) — VI конференция «Проблемы теоретической кибернетики» (Саратов, 1983) — VI международная конференция «Основы теории вычислений (РСТ-87)» (Казань, 1987) — XI Международный семинар «Дискретная математика и её приложения» (Москва, 2012).

Диссертация прошла апробацию на заседаниях семинаров кафедры математической кибернетики факультета ВМиК МГУ им. М. В. Ломоносова (2010;2013), на семинаре по сложности вычислений ВЦ РАН (2013), на Всероссийском научном семинаре «Математические вопросы кибернетики» МГУ им. М. В. Ломоносова (2013).

Публикации. По теме диссертации автором опубликовано 15 научных работ, отражающие основное содержание диссертации, в том числе семь работ в журналах, рекомендованных ВАК РФ [64, 66−71].

Личный вклад автора. Все представленные в диссертации результаты получены лично автором.

Структура и объем диссертации

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

Список литературы

включает 105 наименований на 12 страницах.

Заключение

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

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

Результаты получены с использованием новых методов и подходов, разработанных автором: метод сведения задач о существовании комплексов граней определенного вида к метрическим задачам в единичном кубе (гл. 1, 2) — метод доказательства минимальности или не минимальности комплексов граней на основе порядковых свойств меры сложности (гл. 3, 4), а также новый подход к вероятностному методу доказательства существования объектов с экстремальными характеристиками путем определения вероятностного пространства с параметрическим неравномерным распределением и оптимизацией при подборе параметров (гл. 1, 5).

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

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

Для максимального числа тупиковых (минимальных) комплексов граней функции в кубе Вп получена нижняя оценка по порядку логарифма равная п ¦ 2п с константой 1.35 • 2~5 (0.53 • 2~5). Эта оценка превосходит соответствующую оценку для класса симметрических функций, которая по порядку логарифма равна л/п ¦ 2п с константой д/2/7г, при п > 256 переменных. Данный факт объясняет существование гипотезы о достижимости максимальных значений числа тупиковых и минимальных ДНФ на классе симметрических функций.

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

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

Многие открытые проблемы обусловлены отсутствием критериев минимальности комплексов граней относительно конкретных мер сложности. Например, представляется правдоподобным предположение, что доля булевых функций и переменных, у которых существует единственный минимальный комплекс граней или существует кратчайший и не минимальный комплекс граней, стремится к 0 с ростом п. Справедливость этого предположения означает, что у почти всех функций должно быть хотя бы два минимальных комплекса граней и все кратчайшие комплексы граней являются минимальными. С другой стороны, возникает вопрос о существовании меры сложности С, для которой у почти всех функций есть кратчайшие и не^{-минимальные} комплексы граней.