(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 17
Текст из файла (страница 17)
Таким образом, задача3-С о с к задаче РАЗБИЕНИЕ и теорема 5.6 доказана.ГЛАВА 6. МЕТОДЫ ДОКАЗАТЕЛЬСТВА NPПОЛНОТЫМетоды, используемые при доказательстве результатовоб NP-полноте, меняются в столь же широких пределах, как исами NP-полные задачи, поэтому нет возможностипроиллюстрировать их все. Однако имеется несколько общихприемов доказательства, которые часто встречаются и могутподсказать путь к доказательству NP-полноты новой задачи.Они называются: (а) сужение задачи, (б) локальная замена и(в) построение компоненты.В настоящем разделе, в основном на примерах, мыобъясним, что понимается под каждым из этих приемовдоказательства.
Было бы ошибкой пытаться дать их явноеопределение.Многиедоказательствадопускаютинтерпретации, позволяющие причислить их к любой из этихтрех категорий. Некоторые доказательства так сильно зависятот специфики описания задачи, что их не удаётсяклассифицироватьестественнымобразомв стольограниченном множестве категорий. Так что читателю неследует рассматривать нижеизложенное как попыткуклассификации всех доказательств NP-полноты. Наша цель проиллюстрировать некоторые подходы к доказательству NPполноты, которые с интуитивной точки зрения являютсяконструктивными и привлекательными.В дальнейшем мы опускаем во всех доказательствахпроверку того, что рассматриваемая задача принадлежит NP.Относительно каждой из рассматриваемых ниже задач легкоустановить разрешимость за полиномиальное времянедетерминированным алгоритмом.СУЖЕНИЕ ЗАДАЧИИз трех рассматриваемых приемов доказательства методсужения - самый простой и, вероятно, наиболее часто встречается.Доказательство методом сужения NP-полноты фиксированнойзадачи ПеИР заключается в установлении того, что задача Пвключает в качестве частного случая известную NP-полнуюзадачу ГГ.
Суть в том, чтобы указать дополнительныеограничения, которые требуется наложить на индивидуальныезадачи из П, чтобы получившаяся в результате сужения задачабыла бы эквивалентна ГР. Не требуется, чтобы возникающая врезультате сужения задача была точной копией известной NPполной задачи. Нужно, чтобы между задачами имелосьочевидное взаимнооднозначное соответствие, сохраняющееответы «да» или «нет».Несколько примеров доказательств этого типа ужевстречалось. NP-полнота задачи ТОЧНОЕ ПОКРЫТИЕ 3МНОЖЕС'ГВАМИ была доказана путем рассмотрения средиее индивидуальных задач только тех, в которыхтрехэлементные множества содержат по одному элементу измножеств W, X и Y (где W, X, Y - равномощныенепересекающиеся множества).
Такие задачи идентичнызадаче 3-С. Ранее NP-полнота задачи ОРИЕНТИРОВАННЫЙГАМИЛЬТОНОВ ЦИКЛ была доказана благодаря тому, чтосреди ее индивидуальных задач мы рассматривали только те, вкоторых ориентированный граф вместе с каждой дугой (и, у)содержал противоположно ориентированную дугу ( у, и ) , т. е.индивидуальные задачи, в совокупности образующие задачу,идентичную задаче ГАМИЛЬТОНОВ ЦИКЛ.Метод сужения можно рассматривать как иной взгляд назадачу, а не как стандартный способ доказательства NPполноты.Вместо того чтобы пытаться свести одну изизвестных NP-полных задач к заданной, мы концентрируемвниманиенапоследнейипытаемсяотброситьнесущественные ее детали с тем, чтобы получилась известнаяNP-полная задача.
Ниже приведено несколько примеровзадач, NP-полнота которых доказывается методом сужения.(1) МИНИМАЛЬНОЕ ПОКРЫТИЕУСЛОВИЕ. Задано семейство С подмножеств множества S иположительное целое число К.ВОПРОС. Содержит ли С покрытие множества S размера неболее К, т. е. найдется ли подмножество С 'сС такое, что[ С ' К Я и У c = s?<?шС'Доказательство.
Задача превращается в ТП-3, еслиограничиться только теми индивидуальными задачами, укоторых |С| = 3 для всех множеств се С и K=\S\/3.(2) МНОЖЕСТВО ПРЕДСТАВИТЕЛЕЙУСЛОВИЕ. Задано семейство С подмножеств множества S иположительное целое число К.ИЗВОПРОС. Содержит ли S множество представителей для Смощности, не превосходящей К; т. е. существует липодмножество У с S, такое, что |У| < К и У содержит покрайней мере один элемент из каждого множества семействаС?Доказательство. Задача превращается в задачу ВП, если рассмотреть только те индивидуальные задачи, у которых |с| = 2для всех сеС.(3) ИЗОМОРФИЗМ ПОДГРАФУУСЛОВИЕ.
Заданы два графа G = ( VhE,) и Н = (V2, Е2).ВОПРОС. Содержит ли граф G подграф, изоморфный ШДругими словами, существуют ли такие подмножества VczVj,E<zEi и взаимно-однозначная функция f: V2 —>V, что \V\ = \V2\,\E\ = \E2\ тогда и только тогда, когда. (Ди),Ду)} е ЕЧДоказательство. Задача превращается в задачу КЛИКА, еслирассматривать только те индивидуальные задачи, для которыхН - полный граф, т.
е. те индивидуальные задачи, в которых Е2содержит все возможные ребра, соединяющие вершины V2.(4) ОСТОВНОЕ ДЕРЕВО ОГРАНИЧЕННОЙ СТЕПЕНИУСЛОВИЕ. Заданы граф G=(V,E) и положительное целоечисло К, К< | V\ - 1.ВОПРОС. Существует ли в G остовное дерево, в котором всёвершины имеют степень не более К, т. е. такое подмножествоE<zE\ что \E'\=\V\-\, граф G'=(V,Er) связен и ни одна вершина вV не принадлежит более чем К ребрам из Е'?Доказательство.
Если рассмотреть только те индивидуальныезадачи, в которых К= 2, то задача превращается в задачуГАМИЛЬТОНОВ ПУТЬ.(5) МИНИМАЛЬНЫЙ ЭКВИВАЛЕНТНЫЙ ОРИЕНТИРОВАННЫЙ ГРАФУСЛОВИЕ. Заданы ориентированный граф G = (V,A) и положительное целое число К<\А\.ВОПРОС. Существует ли ориентированный граф G'=(V, А '),такой, что A t А, \А’| < К и для каждой пары вершин и и v из Vв С имеется ориентированный путь от и к v тогда и толькотогда, когда в G имеется ориентированный путь из и к v.Доказательство. Если рассматривать только индивидуальныезадачи, для которых граф G сильно связен, т. е.
содержиториентированный путь от любой вершины к любой другойвершине v и |Х] = |Г], то задача превращается в задачуОРИЕНТИРОВАННЫЙ ГАМИЛЬТОНОВ ЦИКЛ. Отметим,что при таком сужении фактически возникает задачаОРИЕНТИРОВАННЫЙ ГАМИЛЬТОНОВ ЦИКЛ В СИЛЬНОСВЯЗНОМ ОРИЕНТИРОВАННОМ ГРАФЕ, однако NPполнота этой задачи немедленно следует из приведенныхвыше конструкций для задач ГЦ и ОРИЕНТИРОВАННЫЙгц .(6) РЮКЗАКУСЛОВИЕ.
Задано конечное множество U, «размеры» s(w)eZ+, «стоимости» v(w)eZ* для всех ueU, общее ограничение Вна размеры, B e Z \ и значение стоимости KeZ*.ВОПРОС. Существует ли подмножество t/'c U, такое, чтоДоказательство. Если ограничиться рассмотрением толькотаких индивидуальных задач, в которых для всех не U,s(u)=v(u) и В ~ К = /2l,tieUs(u), то задача превращается в задачуРАЗБИЕНИЕ.(7)РАСПИСАНИЕ ДЛЯ МУЛЬТИПРОЦЕССОРНОЙСИСТЕМЫУСЛОВИЕ. Задано конечное множество А заданий»,«длительности» l(d)&Z для всех аеЛ, число meZ«процессоров» и «директивный срок» DeZ?.ВОПРОС. Существует ли разбиение A=AIKjA;\J,...yjAm множества А на т непересекающихся множеств, такое, чтоmax Г Y lift))I а^А()Доказательство.Еслирассматриватьтолькотеиндивидуальные задачи, для которых т = 2 ид - v .2а шА/<«>.то задача превращается в задачу РАЗБИЕНИЕ.В заключение заметим, что из трех обсуждаемыхподходов к установлению NP-полноты метод сужения внаибольшей степени выигрывает от наличия обширногосписка NP-полных задач (сверх основных шести задач и ихвариантов).
Многие возникающие на практике задачипредставляют собой просто более сложные версии задач изсписка NP-полных задач в приложении, и способностьусмотреть этот факт во многих случаях позволяет быстродоказать NP-полноту методом сужения.ЛОКАЛЬНАЯ ЗАМЕНАСводимости, возникающие при доказательстве методомлокальной замены, достаточно нетривиальны, чтобы их всегдаможно было представить в стандартном виде, однако ониостаются относительно несложными.
Этот метод состоит втом, что выбирается характерное свойство известной NPполной задачи, с помощью него образуется семействоосновных модулей, а соответствующие индивидуальные задачизаданной задачи получаются путем единообразной заменыкаждого основного модуля некоторой другой структурой. Сводимость задачи ВЫП к задаче 3-ВЫП относится к этому типу.В ней основными модулями задачи ВЫП были дизъюнкции, икаждая дизъюнкция заменялась набором дизъюнкцийсогласно общему правилу.
Важным моментом здесь являетсято, что каждая замена приводила только к локальномуизменению структуры. Эти замены, по существу, не зависелиодна от другой, за исключением тех случаев, когда ониотражали не подвергавшиеся изменению части исходнойиндивидуальной задачи.Конкретизируем эти общие рассуждения примерами.Сначаларассмотрим задачу распознавания, которая соответствуетзадаче минимизации числа умножений, необходимых длявычисления заданного набора произведений элементарныхтермов. При этом предполагается, что операция умноженияассоциативна и коммутативна.ВЫЧИСЛЕНИЕ СЕМЕЙСТВАУСЛОВИЕ. Задано семейство С подмножеств конечного множества А и положительное целое число J.ВОПРОС.
Существует ли такая последовательность(;;j = у //р ?2”***) 85=3-£/[J[//)»содержащая не более чем / операций типа объединение, чтодля каждого подмножества сеС найдется номер /, /< i < j,такой, что z, совпадает с с? (здесь х, и у, - это либо множествавида {а} для некоторого аеЛ , либо это множество вида zkдлянекоторого к<1, причем х. и>’„ /< /< j, не пересекаются).Теорема 6.1. Задача ВЫЧИСЛЕНИЕ СЕМЕЙСТВА NPполна.Доказательство. Сведем задачу ВЕРШИННОЕ ПОКРЫТИЕ кзадаче ВЫЧИСЛЕНИЕ СЕМЕЙСТВА.
Пусть граф G=(V,E) иположительное целое число К<\V\, определяют условиепроизвольной индивидуальной задачи из ВП.В качестве основных модулей ВП возьмем ребра графаG. Пусть ао новый элемент, не принадлежащий V. Операциялокальной замены замещает каждое ребро {u,v}eEподмножеством {ao,u,v}eС. В результате возникает индивидуальная задача из задачи ВЫЧИСЛЕНИЕ СЕМЕЙСТВА,условие которой полностью определяется следующимиданными:Ас = {{% щ о}: {к, v} <= Е },J ^ K +' \E\.'1Легко видеть, что этуиндивидуальную задачу можно построить за полиномиальноевремя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
