(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 19
Текст из файла (страница 19)
Задано конечное множество А «возможныхдиагнозов»,наборСподмножествмножестваА,представляющий бинарные «тесты» и положительное целоечисло J< |C |.ВОПРОС. Существует ли поднабор С 'с С, \С'\ < J, такой, чтодля любой пары а„ а, возможных диагнозов из А имеется некоторый тест се С', для которого |{а„а;}пс|= 1 (т. е. тест с,различающий а, и а,)?Теорема 6.4.
Задана МИНИМАЛЬНЫЙ НАБОР ТЕСТОВNP-полна.Доказательство. Сведем к этой задаче задачу 3-С. Пустьмножества W, X, Y такие, что |Л'|=|А|=|7 \=q и подмножествоМ £~ W X X X К составляют условие индивидуальной задачииз 3-С.В качестве основного модуля задачи 3-С возьмемупорядоченные тройки из множества М. Операция локальнойзамены вместо каждой тройки т - (w, х, у)е М образуетподмножество {w,x,y}e С. Роль ограничителей играют тридополнительных элемента w0, Хо и уо, не принадлежащиеWuXuY, и два дополнительных теста Wu{w0} и Х и{х0}Окончательно индивидуальная задача МИНИМАЛЬНЫЙНАБОР ТЕСТОВ определяется следующим образом:A ^ W \ J X U r U ( w r M z Q, i/0}fc - {{to, x, у): (ю, X , f/) e M } и { Г и Ы , x U {*<>}},/ =a q2.Легко видеть, что эта индивидуальная задача может быть построена по исходной задаче 3-С за полиномиальное время.Ограничитель налагает определенные ограничения на видвозможных компонент (в данном случае на набор тестов С).Во-первых, набор С должен содержать как Wu{wn}, так иХи{х0} по той причине, что только эти тесты отличают у 0 отw0 и х0.
Далее, поскольку w0, х0, у 0 не принадлежат больше ниодному тесту из С, то каждый элемент множества W\j X\j Yдолжен отличаться от одного элемента w0, х0 или у о ввидутого, что он входит в некоторый дополнительный тест с е С ’ \{Wu{w0}, X < j { x o } } . При этом может быть использовано самоебольшее J-2=q дополнительных тестов. Поскольку каждый изоставшихся тестов содержит ровно по одному элементу измножеств W, X и Y, и, кроме того, множества W, X и Y попарноне пересекаются и каждое из них содержит ровно q элементов,то отсюда следует, что любые q дополнительных тестов из Сдолжны соответствовать q тройкам из М, образующимтрехмерное сочетание.
Обратно, если задано любоетрехмерное сочетание из М, то соответствующие q тестов из Сможно использовать для завершения построения оставшихсятестов в нужном количестве. Таким образом, М содержиттрехмерное сочетание тогда и только тогда,когда вмножестве С существует искомый набор тестов.Хотя в обоих рассмотренных примерах ограничителиочень просты, нужно отдавать себе отчет в том, что это невсегда так. Ограничитель особо сложной конструкции используетсявдоказательствеNP-полнотызадачиОРИЕНТИРОВАННЫЙГАМИЛЬТОНОВПУТЬВПЛОСКОМ ГРАФЕ.
Бывают и другие довольно сложныеограничители.ПОСТРОЕНИЕ КОМПОНЕНТПоследним и наиболее сложным из рассматриваемыхнами методов доказательств NP-полноты является методпостроения компонент. Доказательства NP-полноты задачТРЕХМЕРНОЕ СОЧЕТАНИЕ, ВЕРШИННОЕ ПОКРЫТИЕ иГАМИЛЬТОНОВ ЦИКЛ, приведенные ранее, представляютсобой типичные примеры доказательств этого типа.Основная идея таких доказательств заключается в том,чтобы с помощью составных частей рассматриваемой задачисконструировать некоторые «компоненты», соединяя которыеможно «реализовать» индивидуальные задачи известной NPполной задачи.
В трех перечисленных примерах имеются компоненты двух основных типов. Одну из них можно рассматривать как компоненту, «делающую выбор» (например,выбирающую вершины, выбирающую значение истинностипеременных), а другую - как компоненту, «проверяющуюсвойства» (например, проверяющую, что каждое ребропокрыто или что каждая дизъюнкция выполнена).В рассматриваемой индивидуальной задаче этикомпоненты связаны так, что выбранные значения передаютсякомпонентам, проверяющим условия, и последние проверяют,удовлетворяют ли сделанные выборы значений необходимымусловиям. Взаимодействие компонент осуществляется спомощью прямых связей (таких, например, как ребра,соединяющие компоненты набора значений истинности скомпонентами проверки выполнения, условий в сводимостизадачи 3-ВЫП к задаче ВП, а также с помощью глобальныхограничений (таких, например, как общая граница К всводимости задачи 3-ВЫП к задаче ВП, которая наряду соструктуройкомпонентобеспечивает,чтобыкаждаякомпонента наборов значений истинности содержала вточности одну вершину из покрытия и каждая компонентапроверки свойств содержала ровно две вершины этогопокрытия).Вообще говоря, любое доказательство можно считатьоснованным на методе построения компонент, есликонструируемая в нем индивидуальная задача представляетсобой набор компонент, каждая из которых выполняетопределенные функции, формулируемые в терминах исходнойзадачи.
Общая сводимость, примененная ранее длядоказательства теоремы Кука, является хорошим примеромдоказательства этого типа. При этом каждая из шести группдизъюнкций представляет собой один из типов компонент.Посколькудоказательстваметодомпостроениякомпонент часто оказываются довольно длинными и примерытаких доказательств уже рассматривались, то в настоящемразделе мы приведем еще только один пример. Этот заключительный пример, отличающийся от стандартных, иллюстрирует подход, который оказался полезным для сведениязадачи КЛИКА к другим задачам. Здесь доказывается NPполнота задачи теории расписаний, близкой по формулировкек задаче УПОРЯДОЧИВАНИЕ ВНУТРИ ИНТЕРВАЛОВ, рассмотренной в предыдущем подразделе.УПОРЯДОЧЕНИЕ С МИНИМАЛЬНЫМ ЗАПАЗДЫВАЕМ.УСЛОВИЕ.
Заданы множество Т «заданий», каждое изкоторых имеет длительность 1 и «директивный» срок d{t)& Z ,частичное упорядочение < на Т и неотрицательное целоечисло К < Т.ВОПРОС. Существует ли «расписание» <т: Г-» {0,1,..., ]Г|-1}такое, что:( 1 ) a{t)^a{t') при Ш'\(2 ) o(t)<o{t') при t<t';3) \{te Т: o {t)+ l> d (t)}\< iaТеорема 6.5.ЗадачаУПОРЯДОЧЕНИЕСМИНИМАЛЬНЫМ ЗАПАЗДЫВАНИЕМ NP-полнаДоказательство. Пусть граф G = (V, Е) и положительноецелое число J, J<\V\, образуют произвольную индивидуальнуюзадачу КЛИКА. Соответствующая индивидуальная задача иззадачиУПОРЯДОЧЕНИЕСМИНИМАЛЬНЫМЗАПАЗДЫВАНИЕМ имеет множество заданий T=VkjE, К=\Е\J(J-1)/2. Частичное упорядочение заданий определяетсяследующим образом:/' «5 Е и вершина / инцидентна ребру /'/ ( У Н-1)/2, если / € £ ;W Ж В\ если / е У ;Таким образом, «компонента», соответствующая каждойвершине, состоит из единственного задания с директивнымсроком \V\ + |Е\, а «компонента», соответствующая каждомуребру, состоит из единственного задания с директивнымсроком J(J+1)/2.
Благодаря наличию частичного порядка намножестве Т в искомом расписании задание, соответствующееребру, следует за заданиями, соответствующими его концам, ипоэтому задания, длякоторых имеется опасностьзапаздывания (т. е. завершения уже после директивногосрока), обязательно соответствуют ребрам. Искомоерасписание удобно представлять себе схематически, какпоказано на рис. 6.3.
Часть расписания до директивного сроказаданий, соответствующих ребрам, можно рассматривать как«компоненту выбора клики».Btftnamш тРфаmmг----- >---- -----------Jш - т If И \Е\-Ш-\)ЦЫшща- Утщ, cm- twmtm ЗшкмщвжЬвютбуяаШищ- Шщтфщиекрт рфт ЩЩтшЩМ >ктрфш~~оЩ )2---- -щш——-»►| р |+ | с 1Рис 6.3 Диаграмма искомого расписания для индивидуальной задачиУПОРЯДОЧЕНИЕ С МИНИМАЛЬНЫМ ЗАПАЗДЫВАНИЕМ,соответствующая КЛИКЕ размера J.До этого срока может быть выполнено не более J(J+1)/2заданий.
Для того чтобы число запоздавших заданий непревосходило заданной величины К, по крайней мере J(J-1)/2из «ранних» заданий должны соответствовать ребрам. Однакоесли задание, соответствующее ребру, выполняется ранеесвоего директивного срока, то и задания, соответствующие егоконцевым вершинам, также должны быть закопчены раньшеэтого срока.
Минимально возможное число вершин, которыемогут быть инцидентны J{J-1)/2 различным ребрам, равно J(причем это может быть тогда и только тогда, когда эти ребраобразуют полный граф на этих J вершинах). Отсюда следует,что среди «ранних» заданий должно быть но крайней мере Jзаданий,соответствующихвершинам.Однакододирективного срока заданий, соответствующих ребрам, можетбыть выполнено не более/ ('/ - Ь1 1 ”) / 2 — / ( / — 1 ")/2 =/ задании, которые отвечаютвершинам. Следовательно, в любом таком расписании додирективного срока заданий, соответствующих ребрам,должно закончиться ровно J заданий, отвечающих вершинам,и ровно J(J-1)/2 заданий, соответствующих ребрам, которые всовокупности соответствуют клике на J вершинах в графе G.Обратно, если граф G содержит полный подграф на Jвершинах, то искомое расписание можно построить способом,указанным на рис.
6.3.УПРАЖНЕНИЯПриведём двенадцать NP-полных задач, доказательстваNP-полноты которых предоставляются читателю. Ни одна изэтих задач не требует сложного доказательства, поэтому мысоветуем попытаться найти их все. В этих доказательствах вкачестве известных NP-полных задач достаточно использоватьтолько задачи, упоминавшиеся ранее. Для облегчениярешения задачи сгруппированы по методам доказательства.Однако читатель может не обращать внимания на этиуказания, если другой путь доказательства покажется емуболее перспективным.Метод сужения1. САМЫЙ ДЛИННЫЙ ПУТЬУСЛОВИЕ, Залечи граф <? — (К, £) и положительное нелоо число/С< (V|.ВОПРОС. Имеется ли в С простои путь (т.е. путь, нс проходящий дважды ни через одну Вершину.), соцтрявшв не менее чем из К ребер?2. УПАКОВКА МНОЖЕСТВУСЛОВИЕ, Заданы -семейство С конечных множеств и положительноецелое число К, К |Cj.ВОПРОС, Верно ли, что в С имеется К нсиерешшощнхея множеств?3.
РАЗБИЕНИЕ НА ГАМИЛЬТОНОВЫ ПОДГРАФЫУСЛОВИЕ. Заданы гмЛ 0«={Р, £) и положительное целое числаК,К < \ V\,ВОПРОС. Можно ли множество вершин графа G разбить ,на i.sg К««пересекающихся подмножеств Vj, Гг» . К* так, чтобы для всех i(i ag: i tg. к) каждый подграф, индуцированный под множеством Г,-, содержал гамильтонов цикл?4. НАИБОЛЬШИЙ ОБЩИЙ ПОДГРАФУСЛОВИЕ. Заданы графы = (Г,, £(), Сг = (V*. £*} н положительноеаддое число /СВОПРОС Существуют ли такие подмножества £{ s £, и sчт0| В ^ 1 ш j Е'%К , а подграфы | = » { У 5 £ { }Щ ) изоморфны?йги5, МИНИМУМ СУММЫ КВАДРАТОВУСЛОВИЕ. Заданы конечное множество А, «размер» s(a)e Z* для каждого а е:А л положительные целые числа К и АВОПРОС. Могут ли элементы изАбыть разбиты аа К ««пересекаю-Квдхся множеств Ж, А * ,.,,, А* так, что T V £т (s)y < /?Метод локальной яамеиы6, МНОЖЕСТВО ВЕРШИН, РАЗРЕЗАЮЩИХ КОНТУРЫУСЛОВИЕ, Заданы ориентированный граф О * * ( V , А ) ш положительноецелое число К, К я? | / | .ВОПРОС, Существует ли такое подмножество У s V, что |Р'[а£ К нлюбой ориентированный цикл в G содержит по крайней мере одно реброиз Г?7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
