Частичная классификация сложных задач - NP-полнота и вычислительная неразрешимость

Мы подошли к концу главы, в которой была предоставлена довольно обширная подборка NP-полных задач. В некотором отношении полезно знать побольше разных NP-полных задач: когда вы обнаруживаете новую задачу X и хотите доказать ее NP-полноту, нужно продемонстрировать Y≤_PX для некоторой известной NP-полной задачи Y — и чем шире выбор для Y, тем лучше.

В то же время чем больше вариантов найдется для Y, тем труднее может быть выбрать правильный вариант для конкретного сведения. Конечно, вся суть NP-полноты заключается в том, что одна из этих задач работает в сведении в том, и только в том случае, если работают все (так как они эквивалентны в отношении сведения с полиномиальным временем), но сведение к конкретной задаче X от некоторых задач может быть намного, намного проще, чем от других.

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

Задачи упаковки

Задачи упаковки обычно имеют следующую структуру: дан набор объектов, требуется выбрать не менее к из них. Задача усложняется потенциальными конфликтами между объектами, которые не позволяют выбрать некоторые группы одновременно.

В этой главе были представлены две основные задачи упаковки.

♦ Задача о независимом множестве: для заданного графа G и числа k содержит ли граф G независимое множество с размером не менее k?

♦ Задача упаковки множества: для заданного множества U из n элементов, набора S₁, ..., S_m подмножеств U и числа k существует ли набор из минимум k таких подмножеств, из которых никакие два не пересекаются?

Задачи покрытия

Задачи покрытия образуют естественный контраст с задачами упаковки. Как правило, для них характерна следующая структура: дан набор объектов, из которого выбирается подмножество, в совокупности достигающее некоторой цели. Требуется достичь этой цели с выбором только k объектов.

В этой главе были представлены две основные задачи покрытия.

♦ Задача о вершинном покрытии: для заданного графа G и числа k содержит ли G вершинное покрытие с размером не более k?

♦ Задача покрытия множества: для заданного множества U из n элементов, набора S₁, ..., S_m подмножеств U и числа k существует ли набор из не более чем k таких множеств, объединение которых равно всему множеству U?

Задачи разбиения

Задачи разбиения подразумевают нахождение всех способов деления совокупности объектов на подмножества, при которых каждый объект входит ровно в одно подмножество.

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

♦ Задача о трехмерном сочетании: для заданных непересекающихся множеств X, Y и Z, каждое из которых имеет размер п, и заданного множества T ⊆ X x Y х Z упорядоченных триплетов, существует ли в T такое множество из п триплетов, что каждый элемент X U Y U Z содержится ровно в одном из этих триплетов? Другая базовая задача разбиения — задача раскраски графа — встречается тогда, когда вы пытаетесь организовать разбиение объектов при наличии конфликтов (конфликтующие объекты не могут входить в одно множество).

♦ Задача о раскраске графа: для заданного графа G и границы k имеет ли граф G k-раскраску?

Задачи упорядочения

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

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

♦ Задача о гамильтоновом цикле: содержит ли заданный направленный граф G гамильтонов цикл?

♦ Задача о гамильтоновом пути: содержит ли заданный направленный граф G гамильтонов путь?

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

♦ Задача о коммивояжере: для заданного набора расстояний между n городами и границы D существует ли маршрут, длина которого не превышает D?

Численные задачи

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

♦ Задача о суммировании подмножеств: задано множество натуральных чисел w₁, ..., w_n и целевое число W. Существует ли подмножество {w₁, ..., w_n}, сумма которого равна ровно W?

Естественно попытаться применить сведение из задачи о суммировании подмножеств, когда имеется задача со взвешенными объектами, а целью является выбор объектов с учетом некоторого ограничения на общий вес выбранных объектов. Например, именно это происходит в доказательстве (8.24) при демонстрации NP-полноты планирования с временем доступности и предельным временем.

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

Задачи соблюдения ограничений

Наконец, в этой главе рассматривались основные задачи соблюдения ограничений, включая задачу выполнимости булевой схемы, SAT и 3-SAT. Среди них для планирования сведений более полезной была задача 3-SAT.

3-SAT: для заданного множества условий C₁, ..., C_k, каждое из которых имеет длину 3, по множеству переменных X = {x₁, ..., x_n}, существует ли выполняющее логическое присваивание?

Из-за своей выразительности и гибкости задача 3-SAT часто становится полезной отправной точкой для сведений, в которых ни одна из предшествующих пяти категорий не находит естественного соответствия с рассматриваемой задачей. При проектировании сверток 3-SAT будет полезно вспомнить совет, приведенный в доказательстве (8.8) о том, что экземпляр 3-SATможет рассматриваться с двух разных точек зрения: (а) как поиск по вариантам присваивания переменным с учетом ограничения, что все условия должны быть выполнены, и (b) как поиск по вариантам выбора одного литерала из каждого условия с учетом ограничения о невозможности выбора конфликтующих литералов из разных условий. Каждое из этих представлений 3-SATполезно, и каждое формирует ключевую идею для целого класса сведений.