36.20

Блок, соответствующий дизъюнкции (ж V у V z) (задача 36-2).

дизъюнкций, составляющих формулу Lp. На рис. 36.20 показаны рёбра, соответствующие дизъюнкции (хУуУz). Блок, соответствующий каждой дизъюнкции, состоит из 3 вершин для входящих в неё литералов, 5 вспомогательных вершин и вершины true. Перечисленные вершины соединены рёбрами как на рис. 36.20.

e.Докажите, что если в в таком блоке литералы (вершины ж, у, z) имеют цвета c(true) или c(false), то корректная 3-раскраска пяти вспомогательных вершин возможна в том и только том случае, когда хотя бы один из литералов имеет цвет c(true).

f.Завершите доказательство NP-полноты задачи 3-COLOR. Замечания

Прекрасным введением в теорию NP-полноты является книга Гэ-ри и Джонсона [79], содержащая длинный список NP-полных задач из самых разных областей (см. перечисление областей в начале раздела 36.5). Подробное обсуждение NP-полноты и смежных разделов теории сложности вычислений можно найти в книгах Хопкрофта и Ульмана [104] и Льюиса и Пападимитриу [139]. Ахо, Хопкрофт и Ульман [4] также рассматривают NP-полные задачи и сводимость за полиномиальное время (в частности, там рассматривается сведение задачи о вершинном покрытии к задаче о гамильтоновом цикле)

Класс Р был определён в 1964 году Кобэмом [44] и независимо в 1965 году Эдмондсом [61]. Эдмондс определил также класс NP и высказал гипотезу Р ф NP. В 1971 году Кук [49] ввёл понятие NP-полноты и доказал, что задач о выполнимости формулы, а также задача 3-CNF-SAT, являются NP-полными. Независимо определение NP-полноты было дано Левиным, который доказал NP-полноту нескольких задач [138]. Карп в 1972 году предложил метод сведения за полиномиальное время и использовал его для доказательства NP-полноты многих задач [116]. Эта статья Карпа содержит исторически первые доказательства NP-полноты задач о клике, вершинном покрытии и гамильтоновом цикле. К настоящему времени благодаря усилиям многих учёных известны сотни NP-полных задач.

Приведённое нами доказательство теоремы 36.14 заимствовано из книги Пападимитриу и Стайглица [154].

Приближенные алгоритмы

Часто возникшая на практике NP-полная задача настолько важна, что мы не можем позволить себе уклониться от неё, сославшись на NP-полноту. Конечно, надежд построить полиномиальный алгоритм для такой задачи мало. Однако это ещё не значит, что с ней вообще ничего не сделаешь. Во-первых, может оказаться, что какой-то экспоненциальный алгоритм работает приемлемое время на реальных данных. Во-вторых, можно пытаться найти (за полиномиальное время - в худшем случае или в среднем) не оптимальное решение, а некоторое приближение к нему. На практике такое близкое к оптимальному решение может быть вполне достаточным. Алгоритмы, дающие такие решения, называют приближёнными алгоритмами (approximation algorithms). В этой главе мы разберём приближённые алгоритмы для нескольких NP-полных задач.

Оценки качества приближённых алгоритмов.

Пусть мы решаем оптимизационную задачу, то есть ищем объект с наибольшей или наименьшей стоимостью среди множества объектов, на которых задана функция стоимости. Стоимость любого объекта положительна. Мы говорим, что некоторый алгоритм решает такую задачу с ошибкой не более чем в р(п) раз (has a ratio bound р(п)), если стоимость найденного им решения (обозначим ее С) отличается от стоимости оптимального (которую мы обозначим С*) не более чем в р(п) раз. Формально это условие записывается так:

max(C/C*,C7C) р(п).(37.1)

Эта запись годится для задач на минимум и на максимум. Если мы ищем максимум, то 0 < С С*, и потому отношение С/С* не превосходит 1, а отношение С*/С показывает, во сколько раз оптимальное решение больше (=лучше) нашего. Для задач на минимум, напротив, 0 < С* С, и отношение С/С* показывает, во сколько раз стоимость нашего решения больше стоимости оптимального. Мы предполагаем, что все стоимости положительны, и поэтому дроби имеют смысл. Заметим, что р(п) не может быть меньше 1, так как взаимно обратные величины С/С* и С*/С не

могут одновременно быть меньше 1.

Можно сказать, что оптимальный алгоритм - это алгоритм, который решает задачу с ошибкой не более чем в 1 раз. Чем ближе к единице оценка ошибки, тем ближе алгоритм к оптимальному.

Иногда удобнее оценивать качество алгоритма, измеряя относительную ошибку (relative error). Она определяется (для каждого входа алгоритма) как отношение

где (как и раньше) С* обозначает стоимость оптимального решения, а С - стоимость решения, даваемого алгоритмом. Относительная ошибка всегда неотрицательна. Говорят, что приближённый алгоритм имеет относительную ошибку не более е[п) (has a relative error bound е(п)), если

для любого входа длины п. Легко проверить, что относительная ошибка е[п) может быть оценена сверху через функцию р(п). Именно,

В самом деле, для задач на минимум это неравенство превращается в равенство. Для задач на максимум е[п) = (р(п) - 1)/р(п); чтобы получить (37.3), достаточно вспомнить, что р(п) 1.

Для многих задач известны приближённые алгоритмы, решающие задачу с ошибкой не более чем в некоторое фиксированное число раз (независимо от длины входа). В этих случаях мы пишем р или е, не указывая аргумента п. В других случаях такие алгоритмы неизвестны, и приходиться довольствоваться алгоритмами, в которых оценка ошибки растёт с ростом п. Например, такова ситуация в задаче о покрытии множествами, которая рассматривается в разделе 37.3.

Для некоторых задач можно улучшать качество приближения (уменьшать относительную ошибку) ценой увеличения времени работы. Такова ситуация с задачей о сумме подмножества (см. раздел 37.4). Эта ситуация заслуживает специального определения.

Схемой приближения (approximation scheme) для данной оптимизационной задачи называется алгоритм, который, помимо условия задачи, получает положительное число е, и даёт решение с относительной ошибкой не более е. Схема приближения называется полиномиальной (polynomial-time approximation scheme), если для любого фиксированного е > 0 время её работы не превосходит некоторого полинома от п (размера входа).

\С -С* С*

\с -с*

(37.3)