Содержание к диссертации
Введение
ГЛАВА I. Системы тестовых уравнений 12
1.1. Основные обозначения и определения 12
1.2. Труднорешаемость систем тестовых уравнений 22
1.3. Сложность произведения левых частей тестовых уравнений 24
1.4. Полиномиальный алгоритм для решения задачи декомпозиции систем тестовых уравнений на оптимальные блоки из двух уравнений 27
1.5. Труднорешаемость задачи декомпозиции систем тестовых уравнений на олоки минимальной сложности, состоящие из трех уравнений 33
ГЛАВА 2. Системы булевых уравнений 44
2.1. Конечнозначные системы уравнений. Труд норешаемость задачи о декомпозиции двухзначных систем на оптимальные олоки из трех уравнений . 44
2.2. Примеры двухзначных систем уравнений, на которых задача декомпозиции на оптимальные 3 -олоки является труднорешаеюй 50
2.3. Общий случай конечнозначных систем 61
ГЛАВА 3. Исследование систем из сметииеских и монотонных шжвдй. системы нельсоновских уравнений 65
3.1. Системы из монотонных функций 65
3.2. Системы из симметрических функций 67
3.3. О сложности произведения левых частей нельсоновских уравнений 70
3.4. Исследование задачи о декомпозиции нельсоновских систем на оптимальные 5 -блоки 75
Литература
- Сложность произведения левых частей тестовых уравнений
- Труднорешаемость задачи декомпозиции систем тестовых уравнений на олоки минимальной сложности, состоящие из трех уравнений
- Примеры двухзначных систем уравнений, на которых задача декомпозиции на оптимальные 3 -олоки является труднорешаеюй
- Системы из симметрических функций
Введение к работе
В диссертации исследуются сложности алгоритмов решения систем булевых уравнений вида
Универсальным методом решения таких систем является приведение левых частей к дизъюнктивным нормальным формам (д.н.ф.) ? - &\_ и сведение системы к одному уравнению
П а*-, - 1 wi
Левая часть построенного уравнения снова приводится к д.н.ф«, после чего нахождение множества всех решений не представляет труда.
Наиболее сложным в данном процессе является этап перехода от формулы .П 2$ і к д.н.ф. Даже при простейших системах булевых уравнений этот этап требует большой памяти и выполнения большого числа операций на ЭВМ» Это делает практически невозможным решение даже при т*;5О-40« Существующие эффективные алгоритмы решения нелинейных булевых систем узко специализированы и существенно используют свойства функций \.сос^... ,осчу Попытки построения более общих алгоритмов связаны, в основном, с разбиением системы на блоки таким образом, чтобы умножение левых частей уравнений, входящих в один блок, приводило бы к д.н.ф. минимальной или достаточно близкой к минимальной. Это позволяет, в некоторой степени, г уменьшать требуемую память и трудоемкость алгоритма, но тогда трудной оказывается сама задача разбиения на блоки. Для решения этой проблемы в работе ставятся и изучаются следующие задачи.
Пусть задана функция алгебры логики (.^,...,^ . Д.н.ф., реализующая эту функцию, называется кратчайшей (минимальной), если она содержит наименьшее число конъюнкций (символов переменных) среди всех эквивалентных ей д.н.ф. Число элементарных конъюнкций (символов переменных) в кратчайшей (минимальной) д.н.ф. называется сложностью кратчайшей (минимальной) д.н.ф. Везде в работе обозначена через СК(^(.СНФ) сложность кратчайшей (минимальной) д.н.ф., реализующей функцию \
Пусть задано целое положительное число П. < m . Блоком из уравнений ( 1 -блоком) называются подмножества из *ъ уравнений системы (I). Если эти уравнения имеют номера i±^ ..* % ч , то соответствующий им блок будем обозначать через ^?{. -»-м?\. \«Пусть В>= \1; л->- 1~ блок из ъ уравнений системы (I). Обозначим
В работе изучаются следующие задачи о декомпозиции систем булевых уравнений на оптимальные блоки.
1. Задача о разбиении на минимальные X -блоки. Дана систе ма булевых уравнений вида (I), где таЪ-^ч*, <\, - целые. Требует ся разбить эту систему на \ -блоки В ^..., 9>^ таким образом,что бы имело место условие max СмСь-Л —* т*^ (2) is I * %
2. Задача о разбиении на кратчайшие блоки. Здесь требуется разбить систему (І) на Ч. -блоки &4_V"> ^ так, чтобы выполни лось условие —» vwtw (з) is us В диссертации рассматриваются сравнительно простые и достаточно хорошо изученные типы систем булевых уравнений, такие, на- пример, как тестовые [_18, 19, 24-261 , нельсоновские [б, 15, 16} и некоторые их обобщения. Данные типы уравнений выбраны для исследования, потому что к ним весьма часто сводятся важные прикладные задачи. Тестовые системы булевых уравнений имеют следующий общий вид у / где U-v с H(vO) * {_ ij -»»v\"J для всех I - 1,..., w» . Другими словами, левая часть тестового уравнения представляет собой дизъюнкцию некоторого подмножества булевых переменных из множества С4. > "- >ЗСуЛ » причем все переменные входят без отрицаний. Системы нельсоновских уравнений имеют вид где левые части уравнений представляют собой дизъюнкции, содержащие все п переменных, но, возможно, с отрицаниями. Тестовые системы уравнений используются при построении минимальных и тупиковых тестов для бинарных таблиц. Так, решение систем тестовых уравнений является главной частью алгоритма построения минимальных тестов для дискретных систем переработки информации {18, 25} , Тестовые системы уравнений используются также при реализации широко распространенного на практике класса тестовых распознающих алгоритмов [її, 18, 24, 26] . Эти системы находят широкое применение и при решении различных задач исследования операций [18] . Нельсоновские системы уравнений решаются при построении сокращенных д.н.ф. слабоопределенных булевых функций [б] и при построении множества представительных наборов признаков в задачах распознавания с помощью алгоритмов типа "Кора" [2, 7, 8, 16] . Для указанных типов систем сравнительно просто решается зада- - 7 -ча оценки сложности д.н.ф., получаемой при умножении уравнений, входящих в один блок разбиения. Тогда трудность задачи разбиения системы на оптимальные блоки выявляется в "чистом" виде. В диссертации для указанных выше систем уравнений исследуются задачи о вычислении сложности разбиения системы на оптимальные блоки с использованием теории сложностей [і, 9, 10] Работа состоит из трех глав, введения и списка литературы. В первой главе подробно изучаются системы тестовых уравнений. В І.І приводятся некоторые используемые в дальнейшем изложении понятия и обозначения. В 1.2 доказывается, что задача нахождения минимального по рангу решения тестовых систем уравнений труднорешаема. Для подтверждения этого факта доказывается эквивалентность задачи нахождения минимального по рангу решения систем тестовых уравнений к известной лГ^полной задаче о нахождении системы представителей из данного набора подмножеств некоторого конечного множества (теорема І.2.І). В 1.3 для систем тестовых уравнений выводится точная формула, позволяющая подсчитать сложность д.н.ф., получающейся после переменжения левых частей таких уравнений и удаления поглощаемых конъюнкций. Формулы вычисления сложностей получаются прямым конструированием. В 1.4 построен полиномиальный алгоритм для решения задачи декомпозиции систем тестовых уравнений на оптимальные блоки из двух уравнений. Этот алгоритм основан на методе Эдмондса нахождения наибольшего паросочетания в графе [4] . Отмечается, что решающий алгоритм применим к системам, для которых легко вычисляется сложность произведения левых частей двух уравнений. Такими, например, являются системы нельсоновских уравнений. В последнем параграфе первой главы доказывается, что аналогичное разбиение системы тестовых уравнений на блоки, составленные из трех уравнений, приводит к ЯГ-полной задаче. Доказательство труднорешаемости дано в теореме 1.5Л. Для этого к задаче разбиения на блоки сводится специальная задача разбиения графа на подграфы и для последней доказывается Я г-полнота. Из полученных результатов следует, что декомпозиция булевых систем даже весьма простого вида на блоки, составленные по крайней мере из трех уравнений, является трудной, и нет оснований ожидать, что для такой декомпозиции может быть найден точный эффективный алгоритм. Фактически показано, что указанные декомпозиции следует выполнять с помощью приближенных методов, а их эффективность следует оценивать на основе опыта практических применений. Вторая глава работы посвящена изучению так называемых конеч-нозначных систем булевых уравнений. Эти системы отличаются тем свойством, что на блоках определенной размерности В значение сложности Uw может принимать не более > различных значений (s = .2, *>,...) . Такие системы называются S -значними, если специально оговорена размерность блоков (или С^, s) -значны-ми, где t - число уравнений, входящих в рассматриваемые блоки). Очевидно, что методом паросочетаний за полиномиальное время разрешима задача разбиения и,в)-значных систем на оптимальные пары уравнений при любом значении S . Но оказывается, что даже при двухзначных системах аналогичное разбиение на 5 -блоки уже становится ЯР -полной задачей (теорема 2.I.I). В 2.1 приведен пример С^>2) -значной системы, которая строится на заранее заданных трехэлементных подмножествах конечного множества X ; С^С^) - Qt на соответствующих этим подмножествам 3-блоках & , а на остальных блоках 0^(} = <Яа , где (Х± < QA . В 2.2 продолжается исследование конечнозначных систем. _ 9 -Приводятся примеры двухзначных систем, которые представляет самостоятельный интерес. Это обстоятельство иллюстрируют, например, следующие теоремы. Теорема 2.2.1, Если система уравнений (I) составлена из функций, минимальные (кратчайшие) д.н.ф. которых состоят только из элементарных конъюнкций ранга п-п. ( i^ccmvt), то задача о разбиении на минимальные (кратчайшие) 3 -блоки остается /Р-пол-ной. Теорема 2.2.2. Если система уравнений (I) составлена из функций, минимальные (кратчайшие) д.н.ф. которых состоят не более чем из трех элементарных конъюнкций, то задача о разбиении на минимальные (кратчайшие) 3 -блоки остается ^Р-ііолной. Все системы уравнений, построенные для доказательства этих и других теорем данного параграфа, являются двухзначными. Теоремы 2.2.1 - 2.2.3 примечательны также тем, что, пользуясь методом их доказательства, можно получать другие классы систем булевых уравнений, на которых задача о декомпозиции систем на оптимальные Ь -блоки является труднорешаемой. Вторая глава диссертации заканчивается разделом ( 2.3), в котором доказывается труднорешаемость декомпозиции (*>$) -знач-ных систем на оптимальные 1 -блоки при произвольных ъ. * "3 и S-Z.Z Как и в предыдущих случаях, доказательство указанного результата основано на принципе сводимости комбинаторных задач. Пусть заданы два булевых набора <*- - Ы\. >-., <*;*) и ^ -Ч^а, ... > ^*) . Говорят, что <* предшествует набору ^ (обозна-чениеоСі^ ), если o6vs ^ для всех l^i.,...>Vv . Функция алгебры логики \ Сое^,>.чос»^ называется монотонной, если для любых <х^ ^ имеет место неравенство ?С2> ?<А)« Функция vCoc^^qc^ называется симметрической, если она инвариантна относительно любой перестановки переменных. В первых двух параграфах третьей - 10 -главы диссертации изучаются системы уравнений, составленные из монотонных и симметрических функций, В 3.1 приведены несколько классов таких монотонных функций, что если система уравнений (I) составлена из функций одного класса, что задача о разбиении на оптимальные блоки труднорешаема. Аналогичный результат доказан также для систем, составленных из симметрических функций (теорема 3.2.1). Примером конечнозначных систем являются системы нельсоновских уравнений. Оказывается, эти системы принадлежат к классу Пк.("5,Ь)* где ПкЛ*>ь) - множество всех (.Ъ,ъ) -значных систем уравнений по кратчайшей д.н.ф. Однако все доказанные в предыдущих разделах теоремы о конечнозначных системах не могут быть распространены на нельсоновские системы, так как последние составляют более узкий класс. Поэтому для нельсоновских систем >1г-полнота оптимальной декомпозиции не следует, например, из общей теоремы 2.3.1. В диссертации доказана Л' -полнота задачи декомпозиции на минимальные Ь -блоки и для таких систем, что требует проведение более тонких конструкций, изложенных в теореме 3.4.1. Однако системы нельсоновских уравнений обладают одним весьма любопытным свойством. В теореме 3.4.1 фактически показана -ДГ-полнота задачи о декомпозиции на минимальные 3 -блоки для нельсоновских систем, принадлежащих классу [")*.(">>l) , т.е. на таких системах, на любом Ь-блоке В которых значение С*(В>^ принимает одно и то же значение ( Ск(Є>")-Уі + і, где Y\ - число переменных в системе уравнений). Это значит, что для таких систем кратчайшим является любое разбиение системы на Ь -блоки. Следовательно, описан класс систем уравнений, для которых задача о разбиении на минимальные 3 -блоки А? -полная, в то время, как аналогичная задача о разбиении на кратчайшие блоки таковой не является (теорема 3.4.2). Отметим также результат, доказанный в теореме 3.4.3. Она формируется следующим образом. Теорема 3.4.3. Если система нельсоновских уравнений принад лежит классу П^ъ,:*4) , то задача о разбиении на кратчайшие 3 блоки разрешима за полиномиальное время. Условие. Заданы набор 01= (Я ,...,(( } подмножеств конечного множества нМ = {1,.«ъ к J и целое положительное число Q Вопрос. Существует ли такое подмножество Н Н(н) , что Ш I S Q и И содержит, по крайней мере, один элемент каждого подмножества из (Н Теорема 1.2,1. В U(vC) существует множество представителей мощности, не более чем Q , тогда и только тогда, когда система (I.2.I) имеет решение ранга, не превосходящего О, . Доказательство. Пусть является множеством представителей для системы 01 . Рассмотрим іг\ -мерный булевый набор ( . « % УЛ , где ( 1, если left 1 \ 0, если і fl\ і I п. Очевидно, что Цо (( s Q и на таком наборе 0 t,..- !) система (I.2.I) превращается в тождество, так как в каждом ее уравнении есть переменная, значение которой равно единице (номера таких переменных совпадают с представителями подмножеств и і, НІ, ... Qvw в (1 , т.е. совпадают с множеством й ). Докажем теперь обратное. Пусть оС = О ,.. х\ - решение системы (I.2.I) ранга L(I.SQ)H Тогда очевидно, что является множеством представителей системы 0t= (и выполняется условие ft I Q . Теорема доказана. Из доказанной теоремы следует, что задача нахождения мини мального по рангу решения системы тестовых уравнений А Г-полна. Из этого факта, вообще говоря, следует и Лг-полнота, например, задачи нахождения решений систем булевых уравнений, заданных в виде д.н.ф. Поэтому, как отмечено во введении, попытки построения общих алгоритмов решения систем булевых уравнений связаны в основном с разбиением систем на оптимальные в некотором отношении блоки, после чего понижается порядок систем, что и дает возможность решать их универсальными или специализированными методами. Все дальнейшее изложение диссертации посвящено изучению задачи декомпозиции систем. Пусть заданы к тестовых уравнений. Наша цель - вывести общую формулу вычисления сложности минимальной (кратчайшей) д.н.ф. функции, равной произведению левых частей этих уравнений. Для удобства мы рассмотрим не сами эти уравнения, а следующую характеристическую матрицу размером к к Y\ ( Y\ - число переменных) где О ІД - 1 тогда и только тогда, когда переменная ОС входит в L -е уравнение. Пусть . Обозначим через Хд количест во тех переменных, которые входят в данные тестовые уравнения ровно 1и раз, причем в те уравнения, которые имеют номера из множества н . Например, 1Х 1,ъ]( равен числу переменных, входящих одновременно только в первое и в третье уравнения. Заменим все такие (одинаковые для дальнейшего в некотором отношении) переменные одним символическим переменным 2 ft Тогда вместо матрицы ІІ можно рассматривать следующую, более простую матрицу Она имеет к строк и SL столбцов (Д ч і\ \ 2. -Ц). Первый столбец в таблице И соответствует новой переменной Z ,...,v\ t которая входит во все к уравнений, второй столбец соответствует переменной Zti,.-,U-i} , и т.д. Прежде чем перейти к выводу основной формулы, напомним, что систему подмножеств НІ.,— НУУЧ конечного множества Я принято называть тупиковым покрытием, если flj.U- U Иы s ft и для каждого I 1 «. І 6 W\ : Теорема I.3.I. Сложность кратчайшей д.н.ф. функции, полученной после перемножения левых частей к тестовых уравнений, вычисляется формулой еде сумма берется по всем тупиковым покрытиям "1 \ Ну множе-зтва й(! ")= (i, , V\ . Рассмотрим следующую задачу. Задана система тестовых уравне НИИ (I.5.I) где U u =: н( - \1 —% J , і s L 5 m .Не нарушая общности, можно предполагать, что m "5 , fy- - целое. Требуется найти такое разбиение системы (I.5.I) на блоки из трех уравнений E i В)Д , ... Вэ , чтобы имело место условие W\(M См (В 0 —- wvln , (1.5.2) где Сн( 0 - сложность минимальной д.н.ф. произведения левых частей уравнений, входящих в блок ЕЪ . В этом параграфе мы докажем ЛР-полноту данной задачи. Доказательство основано на принципе полиномиальной сводимости известной Л\ -полной задачи к данной \$] . В качестве исходных возьмем следующие две задачи: ТОЧНОЕ ПОКРЫТИЕ -МНОЖЕСТВАМИ Условие. Заданы конечное множество X (такое, что\Х\=Ь ) и набор Tit подмножеств множества X , содержащих по три элемента. Вопрос. Верно ли, что WL содержит точное покрытие множества X , т. е. такой поднабор W V t , что любой элемент из X принадлежит ровно одному подмножеству семейства WL РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ) Условие. Задан граф C-(V,E) такой, что для некоторого целого числа fy .VU Ъ , . Вопрос. Можно ли разбить вершины графа Q на \ непересекающихся множеств Vi .-- Vq, , таких, что каждое из них содержит по три вершины, и для всех V;. - t v U \Wl\ -S і- V ребра t U nV , t W; j (v- J принадлежат множеству E Прежде чем приступим к доказательству теоремы об Лг-полноте, сделаем некоторые предварительные построения. Вместо системы тестовых уравнений (I.5.I) будем рассматривать характеристическую матрицу М следующего вида: МИІо И, г.- 7 І-17 , где ц - 1 тогда и только тогда, когда переменная OCj входит в t -е уравнение. Цусть задан граф С- (V,E) С множеством вершин V(\VU 4) и множеством ребер Е . Этому графу поставим в соответствие бинарную матрицу 14(( , которая строится следующим образом. Каждому отсутствующему ребру 1, j( Е ставится в соответствие таблица Н- (С , состоящая из VYV строк и Ъ(т-.2.) столбцов. В L -й строке этой таблицы т- 1 раза подряд пишется 100, а в I -й строке - 010. В остальных строках по диагонали 001, а оставшиеся незаполненными места заполняются единицами (эта таблица изображена на рис. I.5.I). Построив для каждого , Д Q подобные таблицы и разме стив их рядом друг с другом слева направо так, чтобы строки таблиц с одинаковыми номерами последовательно продолжали друг друга, получим матрицу, которую обозначим через М (G4) . Пусть V\ - целое положительное число. Обозначим через М і (л) матрицу, полученную из М(&) повторением каждого ее столбца ровно h раз. ІІ (С будет состоять из таблиц М-- {(X) . Как уже установили выше, сложность минимальной д.н.ф. произведения левых частей 3-х тестовых уравнении вычисляется по формуле Рассмотрим полученную матрицу П( как характеристическую матрицу некоторой системы тестовых уравнений. Из формулы (1.5.3) видно, что для каждой тройки строк (ід 4 Ц этой матрицы (соответственно, для тройки W«.» ;,vKi вершин графа G )сложность минимальной д.н.ф. произведения левых частей соответствующих уравнений будет полиномом: 5.4) Нас будут интересовать коэффициенты при W в этих многочленах. Существуют следующие четыре типа троек вершин в дополнении графа G С S) . 1. Треугольники. Соответствующий коэффициент при V\ для таких троек ( с, , v ] обозначим через а?3 ( чл Х «- ХОЛ ) 2. Тройки с двумя ребрами { і. -Д , v vK между ними (коэффициент при к - % С » » ».,к ). 3. ТрОЙКИ ВерШИН {VL Л/ л , v . С ОДНИМ ребрОМ {Vi/Vi j меж-ду ними (коэффициент при к - 0 г І.,і ). 4. Тройки вершин без ребер между ними (соответствующий коэффициент при Лемма І.5.І. Коэффициенты при W для построенной матрицы М (а вычисляются следующими формулами где через (Mv\ обозначено локальное число вершины л/ е V в дополнении графа U . Доказательство. Рассмотрим произвольные три строки матрицы у. М С с номерами L I, W . Прежде всего заметим, что коэффициент оіг в (1.5.4) образуется только членом 1Х .\ДХа\.\Х-»1 формулы (1.5.3). А это значит, что при вычислении коэффициента играют роль только те столбцы матрицы М {Q,\ , которые в пересечениях со строками і, д, W. имеют единственную единицу. Следовательно, для доказательства леммы достаточно вычислить количест во столбцов с таким свойством в каждом отдельном случае. Докажем, например, лемму для случая коэффициента ( «.j ) (выбрана тройка {v-l4 v; , vH\ вершин графа с единственным ребром { і, /;\ В G ). Условимся называть строки с номерами -u,v в таблице М«Дф реберными. Рассмотрим подматрицу матрицы М(С , образованную строками L/ k . В этой подматрице существуют три типа отрезков, соответствующих таблицам Mwv(C . Это следующие таблицы: 1. Таблицы, не содержащие реберных строк: II ... I 001 I ... I III I ... I III I ... I II ... I III I ... I 001 I ... I III I ... I II ... I III I ... I III I ... I 001 I ... I Как видим, ни один из столбцов таких таблиц не содержит единственную единицу. Следовательно, такие таблицы не играют никакой роли при вычислении о(г( \ ) . 2. Таблицы, содержащие одну реберную строку. Пусть, например, реберная строка лежит на I -й строке матрицы 100 ... 100 ... 100 ... 100 III ... 001 ... III ... III III ... III ... 001 ... III В таких таблицах существует один столбец с единственной единицей на третьем и один столбец с единственной единицей на втором местах (они обозначены звездочкой). А такие таблицы (с единственной реберной строкой на I -м месте) встречаются ровно С Л - і. раз (это следует из построения матрицы М В данном параграфе будет продолжаться исследование задачи декомпозиций на оптимальные блоки для систем вида Все нижеописанные системы уравнений принадлежат классу Г\н ( ,3- (ПкСъ.аЛ . Но они представляют и самостоятельный интерес, так как будут ставиться естественные ограничения на функции {-. , со-ставляющие данную систему уравнений. Определение 2.2.1. Два множества н и В вершин v\ -мерного единичного куба назовем изолированными друг от друга, если выполнены следующие два условия: a)IUuf б) ДЛЯ любых А н и є В» вершины U и не являются соседними. Определение 2.2.2. Поясом ширины к I п-мерного единич ного куба называется множество где через E (-Л обозначен t -й слой куба Е . Демма 2.2Л. В поясе S V к -мерного единичного куба существуют ( 1 попарно изолированных подкубов размерности k , Доказательство. Рассмотрим пояс бЬ ол в Е В нем U+1 слоев с номерами vw wwL,... л vw + k Пусть V\- Ум. и пусть оід. — o n-u все наборы слоя ЕЛ Л » У которых на первых к местах стоят нули (назовем первые к координат этих наборов свободными). Обозначим через %± -- , «Лч наборы, которые получаются соответственно из наборов 5j.»„% k 3 -v\ заменой первых к нулей единицами. Очевидно, что каждая пара [ i, L] определяет подкуб В- размерности k . Все эти подкубы попарно изолированы. Это вытекает из неравенства и из того, что для всех подкубов & ;_ соответствующие вершины в качестве свободных иглеют один и те же координаты. Лемма доказана. Докажем .дополнительно, что построенная система к -мерных подкубов в слое Ь " является тупиковой. Для этого необходимо показать, что к построенной системе подкубов нельзя добавить еще один, который был бы изолирован от остальных. Единственную вершину подкуба порядка к в поясе S + , находившуюся на слое Е. с , назовем нижней вершиной данного подкуба. Пусть подкуб порядка к в рассматриваемом поясе с нижней вершиной не совпадает ни с одной из вершин о . ».-., ( ; ) ) Докажем, что &о обязательно пересекается с одним из подкубов В ... & ( ;, ) Во избежание сложности записи предположим, что свободные координаты набора о 0 находятся рядом друг с другом (они обозначены звездочкой): Вектор о 0 разделен на 6 отрезков R W4 (Ц длиной соответственно i,Kt, Кг К кХ)т. , где Us - число свободных коорди-нат, находившихся в первых к местах вектора 0 , к . - число координат в начальном отрезке длины k , не являющихся свободны-їли и равных единице, к . - число нулевых несвободных координат в начальном отрезке. Рассмотрим подкуб 8 -и со следующей нижней вершиной и покажем, что В 0 пересекается с подкубом Ь1# Это нетрудно проверить, так как следующая вершина принадлежит обошл подкубам: Итак, мы доказали, что к построенной системе подкубов } ЬІ_, ... .j & С к { нельзя добавить еще один, который был бы изолирован от других. Это значит, что построенная система является тупиковой. Замечание. По-видимому, построенная в лемме 2.2.1 тупиковая зтіаковка является наиплотнейшей, но доказать это не удалось. В дальнейшем нам понадобится и следующая очевидная Лемма 2.2.2. Если и Ь изолированные в Е множества, и IL M И\/М " ТУ111" 03116 покрытия максимальными интервалами — 53 — соответственно множеств - тупиковое покрытие максимальными интервалами множества S и &. Теорема 2.2.1. Если система уравнений (2.2.1) составлена из функций, миниглальные д.н.ф. которых состоят только из конъюнкций ранга п-г(і=і 2, п число переменных), то задача разбиение на миншшшые 3 блоки остается ЛР-полной. Доказательство. Докажем эту теорему для случая 1=1 (остальные случаи доказываются аналогично данному). Пусть ТХ1 - множество всех трехэлементных подмножеств множества X . Теорема будет доказана, если для любого разбиения множества Ttfl на два непересекающиеся подмножества Wit и Wla. можно построить такие функции Пусть задана система из w\ нельсоновских уравнений, где vv\ = "5 для некоторого натурального Доказательство, Сведем к нашей задаче Пусть множество X и система его трехэлементных подмножеств XVI определяют индивидуальную задачу о точном покрытии Ъ «-множествами (\Х\= "Ь # Пусть также для каждого Ч X элемент ос; входит не более, чем в три подмножества из WI Как мы уже знаем, задача при этом дополнительном предположении остается ЛР-полной. Построим, как в теореме 1.5,1, граф G , который ставит соответствие каждому элементу ( эс эе оСк4) є Wl модель, изображенную на рисунке. Известно [3] , что построенный таким образом граф Q имеет разбиение на треугольники тогда и только тогда, когда из WI можно выбрать точное покрытие "S -множествами. Назовем вершины Ci, — oclv графа Q вершинами типа ОС , ВерШИНЫ &i_ ... . $4)$уц - ВершИНаМИ ТИПа і , И 2-І. ... } Є»и»ц вершинами типа в . Локальные степени вершин графа G удовлетворяют следующим соотношениям На главной диагонали Т\ стоят единицы. Кроме того, из единиц состоят также I -я и j -я строки. Все остальные элементы таблицы - нулевые. Назовем I ю и і -ю строки в таблице Т; реберными. Рассмотрим произвольные три строки u v t. в таблице Т . Возможны следующие три случая: а) Среди u,v,t две реберные строки Столбец, сплошь состоящий из нулей или единиц, назовем однородными. Как видим, в этом случае есть всего один однородный столбец (единичный). б) Среди iA,v ,-. одна реберная строка, В этом случае однородных столбцов нет: 00. ,.010. ..000. ...0 ХХ..»ХХХ«««ХХХ, ««Х 00,..000...010.,..0 в) Среди tA . реберных строк нет. В этом случае однородными являются все столбцы, кроме трех, следовательно, их число равно m - Ъ . Построив для всех і» Д G G таблицы Т\ д и разместив их рядом друг с другом слева направо так, чтобы строки таблиц с одинаковыми номерами последовательно продолжали друг друга, получим матрицу, которую обозначим через T(G , Эта матрица состоит из - 78 m строк и w \E\ столбцов, где Е - множество ребер графа G . Рассмотрим теперь произвольные три вершины V MV VK графа Q и соответствующие им строки в матрице Т((0 . Возможны 4 случая. В каждом из отдельных случаев, учитывая рассуждения, сделанные выше, можно считать количество однородных столбцов среди данных строк следующим образом 1) YV«. A Vfc\ -треугольник. Тогда, если через к5 1,д,\Л обозначено число однородных столбцов ив подматрице, образованной строками І % А \ і то = (\Е\- t O CA,-,), Y KbV W - IS (3"4,3) 2) Между вершинами УЦЛ/ Л/ - два ребра: WiC si -(Е\- [ (vd+ CVi rvoDCwv-bV Avw - \0 (3.4.4) 3) Между 0/-С)л/. ,л/к - одно ребро: 4) Между i, v; 4 л/к ребер нет: коСмЛЛ - 0Е1-1у + л+у 1)с л-г (3.4.6) (Везде в обозначениях индекс іл в к (1,1, означает число ребер, соединяющих между собой вершины МЛ/;ХЛ7К графа Q ). Пусть ТУЦ - разбиение на треугольники вершин графа (J . - 79 -В этом графе существуют следующие 3 типа треугольников: Л Рассматривая каждый отдельный случай, легко можно установить (учитывая соотношение (3.4.2)), что при любом разбиении вершин графа на треугольники, имеет место равенство Ъ= W\Ln U3CM%V (ъ-Ъ){т \)± ЬУ«А (3.4.7) Пусть \\ " 3 - целое число. Через Ту ( G обозначим матрицу, полученную из T(G) повторением каждого ее столбца ровно К раз. Рассмотрим Ту(с как характеристическую матрицу некоторой системы нельсоновских уравнений. Так как в Ту (с) каждый столбец из T(G) повторяется V\ раз, то никакие две ее строки (если рассмотреть их как вершины единичного куба) не могут быть соседними в Н (v\ = "5wvVv\E\) . Следовательно, при вычислении соответствующих сложностей всегда имеет место третий случай в формуле (3.3.7). Согласно этой формуле имеем: wV(Mt СН(Ь\ = 2 Л- \ кг+ 3 (иили + 1) (3 4 8) Обозначим через к Сці, максимальное число однородных столбцов в подматрице матрицы Ty(G , образованной тремя строками 1,1 , U , где соответствующие этим строкам вершины v-b 4i VH в графе G не составляют треугольник. Покажем, что имеет - 80 место неравенство и4ісі,ілл (3.4.9) Из формул (3.4.3) - (3.4.7) видно, что если вершины V-u , (\/-, V такие, что С Л Н Л + ЯС\л Л 11 » то всегда выполняется равенство (3.4.9) (это легко проверяется). Из соотношений (3.4.2) видно, что для всех Az v /v .: Cvo + cviV , . Следовательно, нам остается проверить только случай, когда сумма локальных степеней принимает значения "9" и (v-4} + ЧС лЛ = 3 Это значит, что все три вершины типа 6 . Так как с, л/; VK не составляют треуголь ник, то вершины эти (вершины типа & ) могут иметь между собой самое большее одно ребро. В случае одного ребра имеем Легко проверяется также случай, когда между рассматриваемыми вершинами ребер нет. Следовательно, в случае ЧС Л + (vO + - 1 - неравенство (3.4.9) имеет место. 2) ЯС О + С Л+ЧС іЛ - \0 Здесь могут иметь место следующие два случая: а) Среди W Vi v - две вершины типа « и одна вершина типа е. . Такие вершины могут быть соединены не более, чем одним ребром.Сложность произведения левых частей тестовых уравнений
Труднорешаемость задачи декомпозиции систем тестовых уравнений на олоки минимальной сложности, состоящие из трех уравнений
Примеры двухзначных систем уравнений, на которых задача декомпозиции на оптимальные 3 -олоки является труднорешаеюй
Системы из симметрических функций
Похожие диссертации на О трудностях решения специальных систем булевых уравнений
