научная статья по теме АЛГОРИТМИЧЕСКИЕ ВОПРОСЫ КОНЪЮНКТИВНОЙ ДЕКОМПОЗИЦИИ БУЛЕВЫХ ФОРМУЛ Математика

Текст научной статьи на тему «АЛГОРИТМИЧЕСКИЕ ВОПРОСЫ КОНЪЮНКТИВНОЙ ДЕКОМПОЗИЦИИ БУЛЕВЫХ ФОРМУЛ»

ПРОГРАММИРОВАНИЕ, 2015, No 3, с. 62-72

- ПЕРСПЕКТИВЫ СИСТЕМ ИНФОРМАТИКИ

У Л . ;>,,;>; 519.712.4, 519.714

АЛГОРИТМИЧЕСКИЕ ВОПРОСЫ КОНЪЮНКТИВНОЙ ДЕКОМПОЗИЦИИ БУЛЕВЫХ ФОРМУЛ

© 2015 г. П. Г. Емельянов* **, Д. К. Пономарев* ***,

* Институт систем, информатики СО РАН, 630090 Новосибирск, пр. Лаврентьева, 6 **Новосибирский государственный университет, 630090 Новосибирск, ул. Пирогова, 2 ***Institut für Künstliche Intelligenz, Universität Ulm, D-89069 Ulm, Deutschland E-mail: emelyanov@iis.nsk.su, ponom@iis.nsk.su Поступила в редакцию 01.12.2014

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

1. ВВЕДЕНИЕ

Декомпозиция булевых формул является важной областью исследований, имеющей длинную историю и широкий спектр приложений. Помимо комбинаторной оптимизации и теории игр и (гипер)графов, следует отметить синтез логических схем, в области которого данная задача привлекла внимание большого числа исследователей и получила наибольшее развитие. Возможность декомпозиции булевых формул связана с такими ключевыми параметрами электронных схем, как размер, скорость срабатывания и потребление энергии. Отчет [1] содержит объемный обзор исследований методов декомпозиции, выполненных до середины 1990-х годов. Результаты следующих 15 лет представлены в [2, 3, 4]. Для того чтобы определить место данной статьи в указанном поле иссследований, рассмотрим несколько ключевых вопросов, связанных с декомпозицией и подчеркнем особенность данной работы.

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

же функции в разных нормальных формах может существенно отличаться, а преобразование из одной формы в другую может быть алгоритмически трудным. В данной статье рассматривается несколько широко известных нормальных форм булевых функций — КНФ, ДНФ, СДНФ и АНФ1 — но не обсуждается вопрос о преобразовании одной в другую. Данного рода представления широко применяются в синтезе схем [1, 5, 6, 7]. Так как для рассматриваемых классов формул их отличия от булевых функций не имеют значения для задачи декомпозиции, понятия формулы и функции используются в данной статье равноправно.

Из указанных выше нормальных форм, исторически КНФ и ДНФ первыми начали широко использоваться в синтезе логических схем. Физическая реализация булевых функций, представленных в СДНФ в виде таблиц поиска (англ. Lookup Tables), используется в последних поколениях программируемых логических интегральных схем — программируемых пользовате-

1 Алгебраическая Нормальная Форма, каноническая форма Рида-Маллера или полином Жегалкина.

лем вентильных матриц (англ. FPGA). Данный подход имеет определенные преимущества над непрограммируемыми схемами и, как следствие, широкие коммерческие перспективы (см. например, [6]). С точки зрения алгебры, Алгебраическая Нормальная Форма является полилинейным полиномом над конечным полем порядка 2. АНФ, по сравнению с КНФ/ДНФ, допускает более компактное представление для некоторых классов булевых функций, используемых для реализации, например, арифметических, кодирующих или шифровальных схем. Некоторые исследователи предполагают, что АНФ-схемы являются, в целом, более экономными по сравнению с ДНФ [8]. Задача декомпозиции позитивных булевых формул (известных также как монотонные формулы), заданных в КНФ/ДНФ, привлекла особое внимание в теории игр и теории оптимизации (обзор соответствующей литературы приводится в [3]). Позитивные ДНФ имеют многочисленные теоретико-множественные и гиперграфовые интерпретации, которые делают это представление интересным для комбинаторных исследований. Бинарные Диаграммы Решений (англ. Binary Decisions Diagrams) лежат вне рамок данной статьи, но несомненно следует отметить, что они также рассматриваются в задачах декомпозиции.

Виды декомпозиции. Типичной задачей декомпозиции булевой функции F является отыскание ее представления в виде F = Fi 0 ... 0 Fk, где 0 £ {OR, AND, XOR}. Декомпозиция на две компоненты (бидекомпозиция) — наиболее естественный случай, даже если это не формулируется явно, именно он чаще всего рассматривается в литературе: [3, 5, 7, 9, 10, 11, 12], а также [4 (гл. 3-6)]. Бидекомпозиция имеет вид

F(X) = n(Fi(£b A),F2(£2, А)), где п £ {OR, AND, XOR} А С X, и {£ь £2}

разбиение множества переменных X \ А. Декомпозиция, имеющая большее количество компонент, может быть получена итеративным применением бидекомопозиции к уже выделенным компонентам. Следует отметить, что форма представления компонент может поменяться в сравнении с представлением исходной функции F. В случае А = 0 декомпозиция называется дизъюнктной и считается оптимальной по многим причинам. Иногда к декомпозиции

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

Широко известным примером бидекопозиции является ОН Л.Х1) ра южсннс Шэннона:

Г = хГх=1 V -хГх=о = (х V Гж=о)(-х V Гх=1).

В некотором смысле, полное решение задачи би-декомпозиции произвольных функций было дано в серии статей Штейнбаха и других исследователей (см., например, [2]). Показывается, что если задано разбиение переменных по принадлежности к компонентам, то можно проверить, существует ли такая декомпозиция, и предъявить эти компоненты. Однако отыскание разбиения — отдельная сложная задача и, кроме того, некоторые шаги, используемые в проверке, являются трудоемкими.

Биох исследовал вычислительную сложность задачи модулярной декомпозиции, основанной на обобщенном разложении Шэннона [3, 13]. Множество переменных А называется модулярным множеством булевой функции Г (X), если Г может быть представлена в виде Г(X) = Н(С(А),Б), где {А, В} — разбиение X, а Н, С некоторые булевы функции. Функция С(А) называется компонентой Г, и модулярная декомпозиция Г конструируется посредством итеративной декомпозиции таких компонент в меньшие. Показано, что в общем случае проблема определения модулярности множества переменных является «^Р-полной. Для позитивных ДНФ предложен алгоритм, имеющий полиномиальную сложность: отыскание модулярного дерева, представляющего все модулярные множества монотонной функции, требует 0(и5М) шагов, где п — количество переменных и N — количество конъюнктов в ДНФ представлении.

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

ется, что даже этот специальный случай декомпозиции является сс^Р-полным для функций, заданных в КНФ и ДНФ. С другой стороны, доказывается существование полиномиальных алгоритмов для положительных КНФ/ДНФ, а также С ДНФ и АНФ. Является неочевидным, применима ли техника Биоха для конъюнктивной декомпозиции позитивных ДНФ. Однако следует отметить, что идея вычисления компонент декомпозиции, используемая в Лемме 2 данной статьи, напоминает заключительный шаг конструирования компонент в [3 (разд. 2.9)].

Отыскание разбиения переменных. Можно сказать, что это главная проблема в декомпозиции булевых функций. Действительно, для многих представлений функций, если разбиение задано, то построение компонент декомпозиции, если она вообще существует, это простая задача. Конструирование модулярных множеств для монотонных ДНФ [3, 13] — один из возможных путей нахождения разбиения. В целом возможны несколько стратегий. Либо множества переменных А, £1, £2 выбираются в качестве кандидатов перед запуском алгоритма [5, 7, 9], а значит он может закончиться неудачей, если они выбраны некорректно, либо эти множества конструируются в процессе работы алгоритма декомпозиции [4 (разд. 5, 6)] и [11].

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

могут отличаться от алгебраических факторов [4 (разд. 4)].

Стандартным алгебраическим представлением булевых функций являются полиномы, обычно над конечными полями, среди которых F2 (поле Галуа порядка 2) наиболее известное. Тогда конъюнктивная декомпозиция соответствует факторизации полилинейных полиномов над F2. Следует отметить, что в общем случае, когда полиномы не являются полилинейными, различают декомпозицию и факторизацию полиномов. Современное состояние данной проблемы широко представлено в [14], хотя и не содержит важного результата Шпилька и Волкови-ча, представленного в 2010 году [

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком