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

ВВЕДЕНИЕ.

ГЛАВА I. СИСТЕМЫ ТЕСТОВЫХ УРАВНЕНИЙ.

§ I.1. Основные обозначения и определения

§ 1.2. Труднорешаемость систем тестовых уравнений.

§ 1.3. Сложность произведения левых частей i :" тестовых уравнений

§ 1.4. Полиномиальный алгоритм для решения задачи декомпозиции систем тестовых уравнений на оптимальные блоки из двух уравнений.

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

ГЛАВА 2. К0НЕЧН03НАЧНЫЕ СИСТЕМЫ БУЛЕВЫХ УРАВНЕНИЙ

§ 2.1. Конечнозначные системы уравнений. Труднорешаемо сть задачи о декомпозиции двухзначных систем на оптимальные блоки из трех уравнений

§ 2.2. Примеры двухзначных систем уравнений, на которых задача декомпозиции на оптимальные 3 -блоки является трудноре-шаеюй

§ 2.3. Общий случай конечнозначных систем

ГЛАВА 3. ИССЛЕДОВАНИЕ СИСТЕМ ИЗ ШМЕТ1ШЕСКИХ И МОНОТОННЫХ ШЖВДЙ. СИСТЕМЫ НЕЯЪСОНО

ВСКИХ УРАВНЕНИЙ.

§ 3.1. Системы из монотонных функций.

§ 3.2. Системы из симметрических функций

§ 3.3. О сложности произведения левых частей нельсонов ских уравнений.

§ 3.4. Исследование задачи о декомпозиции нельсоновских систем на оптимальные

5 -блоки.

В диссертации исследуются сложности алгоритмов решения систем булевых уравнений вида

Универсальным методом решения таких систем является приведение левых частей к дизъюнктивным нормальным формам (д.н.ф.) ? -и сведение системы к одному уравнению

П af-, - 1 wi

Левая часть построенного уравнения снова приводится к д.н.ф., после чего нахождение множества всех решений не представляет труда.

Наиболее сложным в данном процессе является этап перехода от w, формулы .П к д.н.ф. Даже при простейших системах булевых с* 4. уравнений этот этап требует большой памяти и выполнения большого числа операций на ЭВМ, Это делает практически невозможным решение даже при т^ 30-40* Существующие эффективные алгоритмы решения нелинейных булевых систем узко специализированы и существенно используют свойства функций ^дос^. ,осчу Попытки построения более общих алгоритмов связаны, в основном, с разбиением системы на блоки таким образом, чтобы умножение левых частей уравнений, входящих в один блок, приводило бы к д.н.ф. минимальной или достаточно близкой к минимальной. Это позволяет, в некоторой степени, '.уменьшать требуемую память и трудоемкость алгоритма, но тогда трудной оказывается сама задача разбиения на блоки. Для решения этой проблемы в работе ставятся и изучаются следующие задачи.

Пусть задана функция алгебры логики ?(^c^^oc*4) . Д.н.ф., реализующая эту функцию, называется кратчайшей (минимальной), если она содержит наименьшее число конъюнкций (символов переменных) среди всех эквивалентных ей д.н.ф. Число элементарных конъюнкций (символов переменных) в кратчайшей (минимальной) д.н.ф. называется сложностью кратчайшей (минимальной) д.н.ф. Везде в работе обозначена через сложность кратчайшей (минимальной) д.н.ф., реализующей функцию { .

Пусть задано целое положительное число t <• m . Блоком из уравнений ( 1 -блоком) называются подмножества из *ъ уравнений системы (I). Если эти уравнения имеют номера . , i.^ , то соответствующий им блок будем обозначать через Пусть блок из ъ уравнений системы (I). Обозначим

СкСвЬСкС?^.^?^)

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

1. Задача о разбиении на минимальные X -блоки. Дана система булевых уравнений вида (I), где ^ - целые. Требуется разбить эту систему на \ -блоки таким образом,чтобы имело место условие max СM(£>L) —* (2) is v *

2. Задача о разбиении на кратчайшие блоки. Здесь требуется разбить систему (I) на 1 -блоки &^ так, чтобы выполнилось условие

W\ (Л v wlw (з) is u$ <v

В диссертации рассматриваются сравнительно простые и достаточно хорошо изученные типы систем булевых уравнений, такие, например, как тестовые 19, 24-261 , нельсоновские [б, 15, 16} и некоторые их обобщения. Данные типы уравнений выбраны для исследования, потому что к ним весьма часто сводятся важные прикладные задачи. Тестовые системы булевых уравнений имеют следующий общий ввд у /

J € h

ДЛЯ BCeX L - X . . vv\ Другими словами, левая часть тестового уравнения представляет собой дизъюнкцию некоторого подмножества булевых переменных из множества > -- » причем все переменные входят без отрицаний. Системы нельсоновских уравнений имеют вид

I\ = V ^ v ос!- = 1 > и» C^v , где левые части уравнений представляют собой дизъюнкции, содержащие все п переменных, но, возможно, с отрицаниями.

Тестовые системы уравнений используются при построении минимальных и тупиковых тестов для бинарных таблиц. Так, решение систем тестовых уравнений является главной частью алгоритма построения минимальных тестов для дискретных систем переработки информации {18, 25} , Тестовые системы уравнений используются также при реализации широко распространенного на практике класса тестовых распознающих алгоритмов [п, 18, 24, 26 ] . Эти системы находят широкое применение и при решении различных задач исследования операций [18] .

Нельсоновские системы уравнений решаются при построении сокращенных д.н.ф. слабоопределенных булевых функций [б] и при построении множества представительных наборов признаков в задачах распознавания с помощью алгоритмов типа "Кора" [2, 7, 8, 16] .

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

В диссертации для указанных выше систем уравнений исследуются задачи о вычислении сложности разбиения системы на оптимальные блоки с использованием теории сложностей [i, 9, 10] •

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

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

В § I.I приводятся некоторые используемые в дальнейшем изложении понятия и обозначения.

В § 1.2 доказывается, что задача нахождения минимального по рангу решения тестовых систем уравнений труднорешаема. Для подтверждения этого факта доказывается эквивалентность задачи нахождения минимального по рангу решения систем тестовых уравнений к известной ^Р-полной задаче о нахождении системы представителей из данного набора подмножеств некоторого конечного множества (теорема I.2.I).

В § 1.3 для систем тестовых уравнений выводится точная формула, позволяющая подсчитать сложность д.н.ф., получащейся после переменжения левых частей таких уравнений и удаления поглощаемых конъюнкций. Формулы вычисления сложностей получаются прямым конструированием.

В § 1.4 построен полиномиальный алгоритм для решения задачи декомпозиции систем тестовых уравнений на оптимальные блоки из двух уравнений. Этот алгоритм основан на методе Эдмондса нахождения наибольшего паросочетания в графе [4] . Отмечается, что решающий алгоритм применим к системам, для которых легко вычисляется сложность произведения левых частей двух уравнений. Такими, например, являются системы нельсоновских уравнений.

В последнем параграфе первой главы доказывается, что аналогичное разбиение системы тестовых уравнений на блоки, составленные из трех уравнений, приводит к ^Р-полной задаче. Доказательство труднорешаемости дано в теореме 1.5Л. Для этого к задаче разбиения на блоки сводится специальная задача разбиения графа на подграфы и для последней доказывается ./fP-полнота. Из полученных результатов следует, что декомпозиция булевых систем даже весьма простого вида на блоки, составленные по крайней мере из трех уравнений, является трудной, и нет оснований ожидать, что для такой декомпозиции может быть найден точный эффективный алгоритм. Фактически показано, что указанные декомпозиции следует выполнять с помощью приближенных методов, а их эффективность следует оценивать на основе опыта практических применений.

Вторая глава работы посвящена изучению так называемых конеч-нозначных систем булевых уравнений. Эти системы отличаются тем свойством, что на блоках определенной размерности В значение сложности может принимать не более £> различных значений Такие системы называются S -значными, если специально оговорена размерность блоков (или С^, s) -значными, где 1 - число уравнений, входящих в рассматриваемые блоки). Очевидно, что методом паросочетаний за полиномиальное время разрешима задача разбиения и,в)~значных систем на оптимальные пары Зфавнений при любом значении S . Но оказывается, что даже при двухзначных системах аналогичное разбиение на 5 -блоки уже становится -полной задачей (теорема 2.1.1). В § 2.1 приведен пример СЪ%2) -значной системы, которая строится на заранее заданных трехэлементных подмножествах конечного множества X ; СмО^- fti на соответствующих этим подмножествам 3-блоках , а на остальных блоках См(е»>) = t где (XL < . В § 2.2 продолжается исследование конечнозначных систем.

- 9

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

Теорема 2.2.1. Если система уравнений (I) составлена из функций, минимальные (кратчайшие) д.н.ф. которых состоят только из элементарных конъюнкций ранга п-п. ( п.- covwt), то задача о разбиении на минимальные (кратчайшие) 3 -блоки остается /Р-пол-ной.

Теорема 2.2.2. Если система уравнений (I) составлена из функций, минимальные (кратчайшие) д.н.ф. которых состоят не более чем из трех элементарных конъюнкций, то задача о разбиении на минимальные (кратчайшие) 3 -блоки остается ^Р-полной.

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

Вторая глава диссертации заканчивается разделом (§ 2.3), в котором доказывается труднорешаемость декомпозиции -значных систем на оптимальные t -блоки при произвольных t ^ Ъ и SmZ • Как и в предыдущих случаях, доказательство указанного результата основано на принципе сводимости комбинаторных задач.

Пусть заданы два булевых набора <*- - Ы\. ог*) и ^ fN" «-J . Говорят, что oL предшествует набору ^ (обозна-чение^^^ ), если oLx s ^ для всех Iа * . Функция алгебры логики ^Соо^.^оь^ называется монотонной, если для любых имеет место неравенство

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

- 10 главы диссертации изучаются системы уравнений, составленные из монотонных и симметрических функций, В § 3.1 приведены несколько классов таких монотонных функций, что если система уравнений (I) составлена из функций одного класса, что задача о разбиении на оптимальные блоки труднорешаема. Аналогичный результат доказан также для систем, составленных из симметрических функций (теорема 3.2.1).

Примером конечнозначных систем являются системы нельсонов-ских уравнений. Оказывается, эти системы принадлежат к классу (Ъ}Ъ)» где ПкЧ^ь) - множество всех -значных систем уравнений по кратчайшей д.н.ф. Однако все доказанные в предыдущих разделах теоремы о конечнозначных системах не могут быть распространены на нельсоновские системы, так как последние составляют более узкий класс. Поэтому для нельсоновских систем ./fP-полнота оптимальной декомпозиции не следует, например, из общей теоремы 2.3.1. В диссертации доказана -полнота задачи декомпозиции на минимальные Ь -блоки и для таких систем, что требует проведение более тонких конструкций, изложенных в теореме 3.4.1. Однако системы нельсоновских уравнений обладают одним весьма любопытным свойством. В теореме 3.4.1 фактически показана ^fR-полнота задачи о декомпозиции на минимальные 3 -блоки для нельсоновских систем, принадлежащих классу Г)к.С2\1) , т.е. на таких системах, на любом Ь-блоке В которых значение принимает одно и то же значение ( + где Y\ - число переменных в системе уравнений). Это значит, что для таких систем кратчайшим является любое разбиение системы на Ь -блоки. Следовательно, описан класс систем уравнений, для которых задача о разбиении на минимальные Ъ -блоки А Р -полная, в то время, как аналогичная задача о разбиении на кратчайшие блоки таковой не является (теорема 3.4.2).

Отметим также результат, доказанный в теореме 3.4,3. Она формируется следующим образом.

Теорема 3.4.3. Если система нельсоновских уравнений принад' лежит классу П^ъ,:*4) , то задача о разбиении на кратчайшие 3 • блоки разрешима за полиномиальное время.

1. Васильев ЮЛ,, Глаголев В.В, Метрические свойства дизъюнктивных нормальных форм. В кн.: "Дискретная математика и математические вопросы кибернетики". М,, Наука, 1974, с. 99-148.

2. Губерман Ш.А., Мартов Т.М. Оценка перспективности местонахождений гидротермальных руд с применением ЭВМ. Труды МИНХ и ГП им. Губкина, вып. 62, М., Недра, 1966.

3. Гэри М., Джонсон Л. Вычислительные машины и труднорешаемые задачи. М., Мир, 1982,

4. Edmonctb 3. tAc\xi.*Y\uw\ and po-tij^ceUovx witV\ O-i VtVtlc.es . 3. o^ Re*.,Af<lt. of Sterol., IH S> k 3 g> , p. MS.

5. Журавлев Ю.И, Алгоритм построения минимальных дизъюнктивных нормальных форм для функций алгебры логики. В кн.: Дискретная математика и математические вопросы кибернетики. М., Наука, 1974, с. 67-98.

6. Журавлев Ю.И. Об отделимости подмножеств вершин v\ -мерного единичного куба. Труды МИАН СССР им. Стеклова, т. 51, М., 1958, с. 143-157.

7. Журавлев Ю.И. Об алгоритмическом подходе к задачам распознавания. В кн.: Проблемы кибернетики, т. 33, М., Наука, 1978, с. 5-68.

8. Журавлев Ю.И. Модель распознающих алгоритмов с представительными наборами и системой опорных множеств. Журнал вычисл. матем. и математ.физики, 1981, т. 21, № 5.

9. Журавлев Ю.И., Коган А.Ю. Нормальные формы для булевых функций с малым числом нулей. ДАН СССР, 1985.Ю. Кристофидес Н. Теория графов: алгоритмический подход. М,, Мир, 1978.

10. Карп P.M. Сводимость комбинаторных проблем. В кн.: Кибернетический сборник", Новая серия, 1975, $ 12.

11. Кук С,А. Сложность процедур вывода теорем. В кн. "Кибернетический сборник", Новая серия, 1975, Jfe 12.

12. Нигматуллин Р.Г. Сложность булевых функций. Издательство Казанского университета. Казань, 1983.

13. SOW R, X. ur»\jpCS"t hoi.WKfc'^ ttw't.lrv Qwv4c"LiOVv S . 3,2.0, Ao 13 55 , \0 5-l0%.

14. Платоненко И.М, 0 реализации алгоритмов типа "Кора" с помощью решения систем булевых уравнений специального вида. Сообщения по прикладной математике. ВЦ АН СССР, М,, 1983.

15. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М., Мир, 1976,

16. Соловьев Н.А. Тесты. Издательство"Наука) Сибирское отделение. Новосибирск, 1978.

17. Соловьев Н.А, 0 безусловных тестах для некоторого класса таблиц. В кн. Проблемы кибернетики' , М., Наука, 1967, Jfc 18,с. 45-66.

18. Сафарян А.А. О решении систем булевых уравнений, возникающих при построении тестов и систем нельсоновского типа. Журнал вычисл. матем. и математ. физики, т. 24, $ 10, М., Наука, 1984.

19. Сафарян А.А, .л(Р-полнота задачи разбиения систем булевых уравнений на минимальные блоки. Сообщения пр прикладной математике. ВЦ АН СССР, М., 1984.

20. Харари К. Теория графов. М., Мир, 1970.

21. Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем. Труды МИАН им. Стеклова, т. 51, 1958, с. 270-360.

22. Яблонский С.В. Функциональные построения в к -значной логике. Труды МИАН, 1958, т. 51, с. 5-142.

23. Яблонский С.В. 0 построении кратных тупиковых экспериментов для автоматов. В кн.: Распознавание образов: труды международного симпозиума 1971 года по практическим применениям методов распознавания образов . ВЦ АН СССР, М., 1973, с. 187-193.