22. Анализ подзадач np-полной задачи. Применение теории np-полноты для анализа задач.

Исследуя любую новую задачу, желательно сначала установить, разрешима ли она полиномиальным алгоритмом или является NP-полной. В первом случае теория NP-полноты не может быть использована для анализа. Во втором же случае, скорее всего, можно будет сказать, что полиномиальных алгоритмов её решений не существует. Однако для большинства задач трудно ответить как на первый, так и на второй вопрос.

В ситуации, которая описана, нельзя полагаться на интуицию, поскольку очень часто NP-полные задачи при незначительном изменении условий превращаются в полиномиально разрешимые. Например, задачи 3-ВЫП и 3-С NP-полны, а близкие им задачи 2-ВЫП и ПАРОСОЧЕТАНИЕ разрешимы за полиномиальное время. Таким образом, при анализе задач лучше пользоваться двухсторонним подходом: с одной стороны пытаться найти полиномиальный алгоритм, а с другой пытаться доказать NP-полноту задачи. Мы рассмотрим ситуацию, когда NP-полнота задачи доказана. Далее будет рассмотрен указанный двухсторонний подход для более глубокого анализа этой задачи.

Анализ подзадач.

Несмотря на то, что некоторая задача является NP-полной, необходим её дальнейший анализ. Это связано с тем, что обычно доказанная задача является некоторой идеализацией решаемой конкретной прикладной задачи. При этом могут быть упущены некоторые конкретные детали исходной задачи. Если мы их примем в учёт, то вполне возможно, что задача станет полиномиально разрешимой. Кроме этого, возможно, что индивидуальные задачи, плохо поддающиеся решению, не очень многочисленны. Вполне возможно, что они обладают некоторыми характерными свойствами, которые позволяют их заблаговременно опознать. Описанные возможности могут быть изучены при помощи анализа подзадач исходной задачи. П’ является подзадачей задачи П, если в ней сформулирован тот же вопрос, что и в П, но только на некотором подмножестве множества индивидуальных задач из П.

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

Очевидно, что если задача П является NP-полной, то её подзадачи могут быть как NP-полными, так и полиномиально разрешимыми. В предположении, что PNP, можно считать, что подзадачи любой NP-полной задачи лежат по разные стороны воображаемой границы, которая разделяет полиномиальные и труднорешаемые задачи. На самом деле, при анализе подзадач лучше в каждый момент представлять себе «пограничную зону» между двумя типами задач. С одной стороны от неё лежат NP-полные задачи, с другой стороны – полиномиально разрешимые, в самой же «пограничной зоне» лежат задачи, NP-полнота которых остаётся под вопросом.

Техника, используемая для доказательства NP-полноты подзадач, аналогична описанной ранее для изолированных задач. Но здесь имеется одно существенное отличие, когда мы пытаемся доказать NP-полноту подзадачи, нам уже известно доказательство NP-полноты некоторой обобщённой версии этой подзадачи. Это сразу нам подсказывает кандидата на известную NP-полную задачу. Кроме того, мы уже имеем доказательство NP-полноты, которое можно попытаться модифицировать для получения доказательства NP-полноты соответствующей подзадачи.

Каждый из представленных результатов об NP-полноте подзадач может быть получен из общей задачи методом локальной замены. Основная идея при доказательстве заключается в замене вершин. Другое общее ограничение для задачи из теории графов состоит в требовании планарности графов.

Граф называется планарным, если его можно отобразить на листе бумаги так, что ни какие два ребра не пересекаются (единственно возможные точки пересечения – общие вершины). Например, при составлении географической карты и при конструировании печатных схем возникают планарные графы. Задача КЛИКА снова даёт нам пример задачи, которая при наложении указанного условия упрощается. Это связано с тем, что никакой планарный граф не может содержать полного подграфа более чем на четырёх вершинах.

Для доказательства NP-полноты ситуации планарных графах обычно используется два подхода:

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

2. Применение локальной замены к исходному графу. Для этого конструируется “переплетение”, которое является планарным графом и которое может быть использовано вместо любого пересечения рёбер при плоскостном изображении графа.