close

Вход

Забыли?

вход по аккаунту

?

33.О сложности дискретных задач

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования Российской Федерации
Ярославский государственный университет им. П.Г. Демидова
Кафедра компьютерных сетей
О сложности дискретных задач
Методические указания
Ярославль 2004
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ББК В 311
О 11
УДК 519.6
Составители В.А. Бондаренко, М.В. Краснов
О сложности дискретных задач: Метод. указания / Сост.
В.А. Бондаренко, М.В. Краснов; Яросл. гос. ун-т. Ярославль, 2004.
23 с.
Приводятся основные факты возникшей тридцать лет назад и уже
ставшей классической теории Кука - Карпа. Внимание читателя акцентируется на содержательных аспектах теории.
Предназначены для студентов, обучающихся по дисциплине
«Методы построения эффективных алгоритмов» (блок СД), специальность 010200 Прикладная математика и информатика, форма обучения очная.
Рецензент: кафедра дискретного анализа Ярославского государственного университета им. П.Г. Демидова.
© Ярославский государственный университет, 2004
© Бондаренко В.А., Краснов М.В., 2004
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В последнее время стало обычным использование терминов "непрерывные задачи" и "дискретные задачи". Установить строгое различие между этими двумя типами математических задач непросто, да
и не представляет особого смысла, так как одна и та же задача может
рассматриваться как непрерывная и как дискретная в зависимости от
выбора подходов к ее решению. Говоря же грубо, можно считать непрерывными те задачи, в постановке которых фигурируют непрерывные множества, например, R – множество всех действительных чисел
и т.п. Для описания дискретных задач используются множества дискретной природы, например целочисленные множества.
Систематический интерес к дискретным задачам возник относительно недавно - несколько десятилетий назад. Формирование соответствующих разделов математики в значительной мере стимулировалось появлением и развитием вычислительной техники. Это
влияние, постоянно возрастая, проявляется в разных направлениях. С
одной стороны, высокопроизводительные компьютеры позволяют
применять методы, связанные с вычислениями большого объема, и
тем самым расширять круг эффективно решаемых задач. С другой
стороны, при конструировании и организации работы современных
вычислительных систем появляются новые математические задачи
дискретного характера.
1. Примеры дискретных задач
Сформулируем несколько задач. Они окажутся полезными в качестве иллюстрации основных понятий, обсуждаемых далее.
Задача КОММИВОЯЖЕРА (ЗК). Имеется n пунктов, расстояния
между любыми двумя из которых известны и представляют собой целые числа. Требуется объехать все пункты, посетив каждый по одному разу и возвратившись в исходный, так, чтобы длина полученного
кольцевого маршрута была наименьшей.
Задача О МИНИМАЛЬНОМ ОСТОВНОМ ДЕРЕВЕ. Здесь исходная ситуация аналогична: имеется n пунктов с заданными целочисленными попарными расстояниями. Требуется спроектировать
минимальную по протяженности дорожную сеть без дополнительных
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
узлов, которая позволяла бы из каждого пункта добраться в любой
другой.
Задача о составном числе. Для заданного натурального числа z
требуется выяснить, является ли оно составным.
Перечень подобного рода задач можно значительно расширить.
Но уже приведенные дают основания для обсуждения достаточно характерных общих вопросов. Прежде всего обратим внимание на термин "задача". В тех постановках, которые даны выше, речь идет о
массовых задачах, так как предполагается, что в двух первых случаях
число пунктов и попарные расстояния между ними могут быть любыми, а в третьей задаче z выбирается также произвольно. Итак, под
дискретной задачей мы будем понимать массовую задачу как совокупность индивидуальных задач, соответствующих всевозможным
конкретным исходным данным. Примером индивидуальной задачи о
составном числе служит такая: выяснить, является ли составным число 12345678910111213.
2. Алгоритмы
Разговор о задаче предполагает рассмотрение средств ее решения, или алгоритмов. Оставляя пока в стороне возможные конкретные алгоритмы, обсудим понятие алгоритма с общей точки зрения.
Так как речь идет о массовой задаче, алгоритм должен уметь воспринимать информацию о каждой индивидуальной задаче, уметь перерабатывать эту информацию и, наконец, выдавать результат решения
каждой индивидуальной задачи. Эти три части, связанные с функционированием алгоритма, назовем соответственно входом, собственно алгоритмом, или программой, и выходом.
Вход алгоритма представляет собой конечную последовательность цифр, обусловленным образом характеризующую индивидуальную задачу. Под длиной входа индивидуальной задачи z будем
понимать количество цифр l(z) в этой последовательности.
Содержательная сторона алгоритма сосредоточена в программе,
выполнение которой начинается с подачи входа и завершается формированием выхода. Работа программы осуществляется в виде некоторой последовательности операций, на каждую из которых затрачивается условная единица времени. Характер используемых операций
и их последовательность определяются выбором вычислительного
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
устройства, программы и входа. Обозначим через A алгоритм некото-
рой задачи, через t A ( z ) – число операций, затрачиваемое алгоритмом A на индивидуальную задачу z, и назовем трудоемкостью алгоритма A функцию
TA (L) = max{t A ( z) : l ( z) ≤ L} .
(1)
Эта функция характеризует зависимость между длиной входа и
временем работы алгоритма. Ясно, что более предпочтительным является такой алгоритм, для которого TA (L) растет как можно медленней.
Обращаясь теперь к третьему элементу алгоритма - выходу, отметим различие между приведенными выше задачами. Именно в задаче о составном числе выход предусматривает лишь два варианта:
"да" или "нет". Задачи подобного вида называются задачами распознавания. Другие две задачи относятся к классу оптимизационных,
или экстремальных, задач.
3. Полиномиальная разрешимость
Задачи рассматриваемого вида объединяет то, что для решения
каждой из них можно использовать простейший алгоритм – алгоритм
прямого перебора, который обозначим через S. Попытаемся грубо
оценить трудоемкость переборного алгоритма для приведенных выше
задач. Для простоты примем, что в первых двух задачах расстояния
между пунктами могут принимать целые значения от 1 до 9. Тогда
длина l ( z) входа индивидуальной задачи z для n пунктов составляет
n(n − 1)
2
. Алгоритм прямого перебора для задачи КОММИВОЯЖЕРА
заключается в вычислении длины каждого кольцевого маршрута и
выборе среди них минимального. Общее число обходов n пунктов
равно, как легко заметить,
(n − 1)!
,
2
и эта величина служит нижней
оценкой числа операций при прямом переборе. Учитывая, что l (z) < n 2
n
и t S ( z) ≥ 2 при n > 5, можем оценить снизу трудоемкость (1) алгоритма S:
TS (L) > 2
L
при L > 10 .
5
(2)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Оценка (2) справедлива и для второй задачи, так как при одном и
том же n общее число остовных деревьев не меньше количества всех
обходов, ведь, "разорвав" кольцевой маршрут, мы получим остовное
дерево.
Проведем аналогичные рассуждения для оценки трудоемкости
прямого перебора в задаче о составном числе. В этом случае длина
входа l ( z) равна количеству цифр в десятичной записи числа z, определяющего индивидуальную задачу, т.е. l (z) < lg z + 1. Будем считать,
что алгоритм последовательно делит z на натуральные числа,
бóльшие единицы и не превосходящие z, до тех пор, пока либо остаток не окажется равным нулю, либо не будут исчерпаны указанные
числа. В первом случае выходом служит "да", во втором - "нет". Для
получения грубой оценки трудоемкости под числом операцией будем
понимать количество выполненных делений. Из этих рассуждений
следует искомая оценка:
TS (L) > 10
L
2
− 1
.
(3)
Чтобы сделать полученные оценки более осязаемыми, прикинем
объем прямого перебора для входа определенной длины. Предположим, что число n пунктов в первых двух задачах равно 100, т.е.
l ( z) = 50 × 99 > 702. Из оценки (2) следует, что для решения индивидуальной задачи придется выполнить не менее 1021 операций. Скорость самых современных ЭВМ не превосходит 1012 операций в секунду. Следовательно, для получения результата придется ждать 109 секунд, или
более 30 лет. Оценка (3) приводит к еще более внушительным цифрам. К сказанному можно добавить, что оценки (2) и (3) весьма грубые, действительный рост функции TS (L) более высок; в то же время
при проектировании интегральных схем возникают задачи, подобные
первым двум, для значений n, значительно превосходящих 100.
Таким образом, алгоритм прямого перебора, хотя и является универсальным для задач рассматриваемого вида, практически оказывается малоэффективным.
Естественно возникает вопрос о конструировании алгоритмов,
принципиально более эффективных, чем примитивный прямой перебор. То, что подобного рода алгоритмы вообще существуют, проиллюстрируем следующим примером.
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рассмотрим индивидуальную задачу О МИНИМАЛЬНОМ ОСТОВНОМ ДЕРЕВЕ. На первом шаге соединим два пункта, расстояние между которыми минимально. Далее на каждом шаге соединяем
ближайшие из оставшихся пар пунктов так, чтобы при этом не появлялось замкнутых маршрутов. Процесс завершаем, когда окажутся
соединенными n − 1 пар пунктов. Нетрудно показать, что в результате
получается искомая дорожная сеть минимальной длины. Описанная
процедура легко реализуется в виде алгоритма G , известного под названием "жадный"; его трудоемкость оценивается сверху:
TG (L) < L2 .
(4)
В упомянутом примере для 100 пунктов число используемых
операций не превосходит 25000000 и потребует нескольких секунд
работы рядового компьютера. Представление об эффективных алгоритмах формализуется следующим определением. Алгоритм A называется полиномиальным, если его трудоемкость удовлетворяет неравенству
TA (L) ≤ αLm ,
где α и m - не зависящие от L константы.
Дискретные задачи, для которых существуют полиномиальные
алгоритмы, принято называть полиномиально разрешимыми, а их совокупность образует класс P.
Из трех сформулированных выше лишь задача О МИНИМАЛЬНОМ ОСТОВНОМ ДЕРЕВЕ определенно лежит в классе P, это следует из полиномиальности "жадного" алгоритма. Для двух других задач в настоящее время полиномиальные алгоритмы неизвестны. В
этой связи возникают принципиальные вопросы, привлекшие за последние 30 лет значительное внимание исследователей. Общий смысл
этих вопросов заключается в следующем. Пусть для некоторой дискретной задачи не удается сконструировать полиномиальный алгоритм, несмотря на серьезные усилия многих математиков (пример задача КОММИВОЯЖЕРА). В чем причина этих неудач: в том, что
такой алгоритм не существует вовсе либо полиномиальный алгоритм
существует, но найти его очень трудно? Сразу же заметим, что этот
вопрос до сих пор остается открытым. Однако попытки найти на него
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ответ привели четверть века назад к созданию теории труднорешаемых задач, основные результаты которой принадлежат С. Куку [1], Р.
Карпу [2] и Л. Левину [3]. Эти результаты оказались в такой мере неожиданными, с одной стороны, и практически важными – с другой,
что сама теория сразу же приобрела классический характер и вызвала
многочисленные дополнительные исследования и публикации. Наиболее полное изложение этой теории содержится в монографии
М. Гэри и Д. Джонсона [4].
4. Алгоритмы с оракулом и класс NP
Задачи распознавания даже на первый взгляд представляются более удобными для рассмотрения по сравнению, например, с задачами
оптимизации. Для того чтобы в дальнейшем говорить только о задачах распознавания, коротко остановимся на приведении к этому виду
других задач. Для иллюстрации выберем задачу КОММИВОЯЖЕРА.
Близкую к ней задачу распознавания обозначим ЗКР и сформулируем
так. Существует ли обход всех пунктов, длина которого не превосходит заданного числа Q? Если предположить существование полиномиального алгоритма для ЗК, то, очевидно, ЗКР тоже полиномиально
разрешима. Но верно и обратное: из того, что ЗКР ∈ P, следует ЗК ∈
P. Для доказательства воспользуемся простой идеей известного метода угадывания задуманного числа с помощью вопросов с ответами
"да" или "нет". Пусть A – полиномиальный алгоритм задачи ЗКР:
TA (L) ≤ αLm , и пусть z – индивидуальная ЗК с n пунктами. Искомая
длина кратчайшего обхода находится среди чисел n, n + 1, ..., 9n. Полагая Q = 5n и применяя алгоритм A для соответствующей ЗКР, мы сумеем почти в два раза уменьшить количество чисел - претендентов
для выхода в индивидуальной ЗК. Повторив описанную процедуру не
более чем log 2 9n + 1 раз, получим решение ЗК. Из неравенства log 2 n < n,
справедливого при всех натуральных n, вытекает полиномиальность
сконструированного алгоритма.
Итак, класс задач распознавания оказывается достаточно универсальным для изучения вопросов сложности. Далее под словом "задача" будет пониматься именно задача распознавания.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пусть z – некоторая задача. Обозначим через ZY совокупность
всех индивидуальных задач, выходом для которых служит "да". Вообразим такую ситуацию. Некто, который знает все, предлагает вам
индивидуальную задачу z и утверждает, что z ∈ ZY . Вы просите доказать это. Можно ли рассчитывать, что всезнающий некто, или оракул,
сможет привести достаточно короткое доказательство? Оказывается,
во многих случаях можно, даже если задача труднорешаема. Обратимся к нашим примерам. В задаче ЗКР оракул может указать порядок обхода пунктов, и остается лишь убедиться, что длина соответствующего замкнутого маршрута не превосходит Q. В другой задаче - о
составном числе - оракулу достаточно предъявить делитель числа и
продемонстрировать, что остаток равен нулю. Эти примеры могут
показаться тривиальными, но если рассмотреть подобную последней
задачу о простом числе, то действия оракула уже перестают быть
очевидными. На основе сказанного приведем неформальное определение класса задач, которые называются недетерминированно полиномиальными, или класса NP. Будем говорить, что задача Z принадлежит классу NP, если существует описание такого оракула, который
доказывает включение z ∈ ZY алгоритмом полиномиальной трудоемкости. Заметим, что P ⊆ NP , так как алгоритм, решающий задачу Z,
можно рассматривать и как алгоритм, устанавливающий включение
z ∈ ZY . Класс NP содержит огромное количество теоретически и практически важных задач, для большинства из них принадлежность
классу NP доказывается просто. Ниже речь будет идти в основном о
задачах из NP.
5. Сравнение задач по сложности
Предположим, что рассматриваются две задачи Z и Z ′. Попытаемся наполнить смыслом фразу «задача Z не более сложна, чем задача Z ′ », учитывая при этом, что принципиальным является вопрос о
полиномиальной разрешимости. Достаточно естественным представляется следующий вариант. Если из предположения о том, что Z ′ ∈ P ,
следует Z ∈ P , то принимается, что Z не сложнее, чем Z ′. Примером
реализации этой идеи может служить рассмотренная выше связь между задачами ЗК и ЗКР. В случае, когда речь идет о задачах распо9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
знавания, сравнение их по сложности более формально описывается
таким определением.
Пусть B − полиномиальный алгоритм, множество входов которого состоит из всех индивидуальных задач z ∈ Z , а выходами служат
z′ ∈ Z ′, и пусть вход z принадлежит ZY в том и только том случае, когда соответствующий выход z′ принадлежит ZY′ . Тогда говорят, что
задача Z полиномиально сводится к задаче Z ′; обозначение: Z ≤ Z ′.
Для примера покажем, что к задаче Z ′ = ЗКР полиномиально сводится задача Z о полном пути (Z = ПП); она отличается от ЗКР тем,
что в ней речь идет о незамкнутом пути, который проходит через все
заданные пункты, начинаясь в каком-либо одном и оканчиваясь в
другом пункте. Пусть z − индивидуальная задача о полном пути, в которой количество пунктов равно n, а ограничение на длину пути - Q.
Добавим еще один - (n + 1) -ый - условный пункт, полагая, что расстояние от него до каждого из n заданных равно единице и Q′ = Q + 2, и
рассмотрим индивидуальную задачу z′ ∈ ЗКР с n + 1 пунктами и ограничением длины обхода, равным Q′. Ясно, что переход от задачи z к
задаче z′ осуществляется полиномиальным алгоритмом и полный
путь, длина которого не превосходит Q, для задачи z существует в
том и только том случае, когда для задачи z′ существует замкнутый
обход всех n + 1 пунктов длины, не превышающей Q′.
6. Задачи, самые сложные
в классе NP
Теперь мы можем определить центральное понятие рассматриваемой теории сложности задач.
Задача Z * называется NP-полной, если Z * ∈ NP и для любой задачи
Z из NP выполняется соотношение: Z ≤ Z * .
Заметим, что приведенное определение приобретает смысл лишь
в случае существования хотя бы одной NP-полной, т.е. самой труднорешаемой в классе NP, задачи. Оказывается, такие задачи не только
существуют, но и составляют большинство задач из NP, для которых
не удалось придумать полиномиальные алгоритмы. Обычно для доказательства NP-полноты какой-либо задачи к ней полиномиально сво10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
дится другая задача, NP-полнота которой установлена ранее. Исключение в этом отношении, очевидно, представляет та задача, NPполнота которой была доказана раньше, чем для остальных. Такой
чести удостоилась задача ВЫПОЛНИМОСТЬ в знаменитой теореме
Кука [1]. Прежде чем сформулировать задачу ВЫПОЛНИМОСТЬ,
введем несколько простых понятий, связанных с логическими, или
булевскими, функциями.
Рассмотрим множество X = {x1 , x1 ,..., xn , xn } переменных, каждая из
которых может принимать два значения: 0 и 1, причем
xi = 1 − xi , i = 1,..., n. Подмножество D = {z1 ,..., zk } ⊆ X назовем дизъюнкцией.
Выберем некоторые значения переменных из X и назовем дизъюнкцию D выполненной, если хотя бы одна zi из D оказалась равной
единице.
Сформулируем теперь задачу ВЫПОЛНИМОСТЬ. Заданы множество X и некоторый набор дизъюнкций D j ⊆ X , j = 1,..., m. Требуется
выяснить, можно ли так выбрать значения переменных xi , i = 1,..., n,
чтобы одновременно оказались выполненными все дизъюнкции
D j , j = 1,..., m.
Теорема КУКА. Задача ВЫПОЛНИМОСТЬ является NP-полной.
Не будем останавливаться на точном доказательстве теоремы, а
ограничимся лишь кратким комментарием. Легко понять, что для доказательства полиномиальной сводимости любой задачи из NP к задаче ВЫПОЛНИМОСТЬ необходимо строгое описание класса NP.
Это, в свою очередь, связано с формализацией вычислительных конструкций, которые в разделе 4 названы алгоритмами с оракулом.
Подходящим аппаратом для такой формализации служат логические
функции (в частности, дизъюнкции), они представляют собой математические модели простейших вычислительных элементов, используемых в компьютерах. Сказанным в некоторой степени объясняется
тот факт, что задаче ВЫПОЛНИМОСТЬ выпало стать первой обнаруженной NP-полной задачей.
В настоящее время количество опубликованных NP-полных задач
составляет много сотен. Только в книге [4] рассмотрено более трехсот таких задач разнообразного содержания. Сформулируем шесть
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
задач, которые образуют набор так называемых основных NP-полных
задач.
1. 3-ВЫПОЛНИМОСТЬ. Задан набор дизъюнкций D j , j = 1,..., m,
на конечном множестве переменных X и D j = 3 при всех j = 1,, m.
Существует ли на множестве X набор значений истинности, при котором выполняются все дизъюнкции D j ?
2. РАЗБИЕНИЕ. Задано множество A = {a i , i = 1,, n}, для каждого
элемента a i ∈ A определен вес s(a i ) ≥ 0. Существует ли такое подмножество A′ ⊆ A, для которого выполнено условие ∑ s(a i ) = ∑ s(a i )?
a i ∈ A′
a i ∉ A′
3. ГАМИЛЬТОНОВ ЦИКЛ. Задан граф G = (V, E ). Верно ли, что G
содержит гамильтонов цикл, т.е. такую последовательность v1 , v2 ,, vn
вершин графа G, что n = V , {vn , v1}∈ E и {vi , vi +1}∈ E для всех i = 1,, n − 1?
4. ТРЕХМЕРНОЕ СОЧЕТАНИЕ. Дано множество M ⊆ W × X × Y,
где W, X , Y - три непересекающихся множества одинаковой мощности: W = X = Y = q. Верно ли, что M содержит трехмерное сочетание,
т.е. подмножество M ′ ⊆ M такое, что M ′ = q и любые два различных
элемента из M ′ не пересекаются?
5. ВЕРШИННОЕ ПОКРЫТИЕ. Заданы граф G = (V, E ) и натуральное число K , K ≤ V . Имеется ли в графе G вершинное покрытие не
более чем из K элементов, т.е. такое подмножество V′ ⊆ V, что V′ ≤ K
и для каждого ребра {u, v}∈ E хотя бы одна из вершин u или v принадлежит V ′ ?
6. КЛИКА. Заданы граф G = (V, E ) и натуральное число K , K ≤ V .
Существует ли в данном графе клика мощностью не менее K , т.е. такое подмножество V′ ⊆ V, что V′ ≥ K и любые две вершины из V′ соединены ребром из E ?
Выбор этих шести задач не случаен, с их помощью удается установить NP-полноту большого количества других задач. Доказательст12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
во NP-полноты этих задач можно найти в монографии [4]. Здесь же
ограничимся анализом задачи 3-ВЫПОЛНИМОСТЬ.
Теорема. Задача 3-ВЫПОЛНИМОСТЬ является NP-полной.
Доказательство. Задача 3-ВЫПОЛНИМОСТЬ принадлежит
классу NP. Оракулу достаточно подсказать лишь набор значений истинности переменных задачи, чтобы за полиномиальное время проверить, будут ли при таком наборе значений выполняться все заданные
трехлитерные дизъюнкции.
Сведем задачу ВЫПОЛНИМОСТЬ к задаче 3-ВЫПОЛНИМОСТЬ.
Пусть X = {x1 , x1 ,, xn , xn } - множество переменных и D = {d1 ,, d m} набор дизъюнкций, определяющих произвольную индивидуальную
задачу ВЫПОЛНИМОСТЬ. Построим набор трехлитеральных дизъюнкций D′, такой, что D′ выполним тогда и только тогда, когда выполним набор D. Набор будет строиться путем замены каждой отдельной дизъюнкции d j ∈ D множеством дизъюнкций D′j на
множестве X исходных переменных и на множестве X′j некоторых
дополнительных переменных, причем переменные из X′j будут использованы только в дизъюнкциях из D′j , т.е.

m
′
X = X    X ′j ,
 j =1 
m
D′ =  D′j .
j =1
Таким образом, нужно только показать, как исходя из d j можно
построить X ′j и D′j .
Пусть d j задается множеством {z1 , z2 ,, zk } ⊆ X.
Рассмотрим следующие случаи:
1
2
1. Если k = 1, тогда X ′j = {y j , y j },
, z1 , y1j , y2j }{
, z1 , y1j , y 2j }{
, z1 , y1j , y 2j }}.
D′j = {{z1 , y1j , y2j }{
{{
}{z , z , y }}.
2. Если k = 2, тогда X′j = {y1j }, D′j = z1 , z2 , y j ,
3. Если k = 3, полагаем X′j = ∅, D′j = {d j }.
i
4. Если k > 3, тогда X ′j = {y j : 1 ≤ i ≤ k − 3},
1
1
1
2
j
D′j = {{z1 , z2 , y1j }} {{yij , zi + 2 , yij+1}: 1 ≤ i ≤ k − 4} {{y kj −3 , zk −1 , zk }}.
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для доказательства сводимости надо показать, что набор дизъюнкций D' выполним тогда и только тогда, когда выполним набор D.
Предположим, что t : X → {T , F } есть набор значений истинности, выполняющий D. Покажем, что t может быть продолжен до набора значений истинности t ′ : X′ → {T , F }, который выполняет D'. Поскольку
переменные в множестве X′ \ X делятся на группы X′j и так как переменные в каждой группе X′j входят только в дизъюнкции D′j , то достаточно показать, как t может быть продолжен на каждое множество
D′j отдельно, и в каждом случае нужно проверить, что выполняются
все дизъюнкции в соответствующем множестве D′j . Например, это
можно сделать следующим образом:
в случае k = 1 и k = 2 дизъюнкции из D′j уже выполнены с помощью t, поэтому t может быть продолжен на D′j произвольно;
в случае k = 3 дизъюнкция D′j выполнима с помощью t;
в случае k > 3 рассмотрим дизъюнкцию D j = {z1 , z2 , zk }. Поскольку
t – выполняющий набор значений истинности для D j , то найдется такое целое q, что zq при t принимает значение T. Если q = 1 или q = 2, то
полагаем t ′( yij ) = F , i = 1,, k − 3. Если q = k − 1 или q = k, то полагаем
t ′( yij ) = T , i = 1,, k − 3. В противном случае полагаем t ′( yij ) = T при
i = 1,  , q − 2 и t ′( yij ) = F при i = q − 1,, k − 3. Такой набор значений истинности обеспечивает выполнение всех дизъюнкций в D′j , поэтому t ′
выполняет все дизъюнкции из D'.
Обратно, если t ′ - некоторый выполняющий набор значений истинности для D', то ограничение t' на переменные из X служит выполняющим набором значений истинности для D.
Следовательно, D' выполним тогда и только тогда, когда выполним D. Теорема доказана.
Следует сказать и о "неопознанных" задачах - тех, для которых не
удалось построить полиномиальный алгоритм и не доказана NP-полнота. Таких задач среди опубликованных относительно немного.
Наиболее известна из них задача о составном числе.
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. Задачи с числовыми параметрами
и сильная NP-полнота
Существует целый класс задач, для которых их принадлежность к
классу NP-полных задач зависит от величины числовых значений,
описывающих данную индивидуальную задачу. Если на числовые
значения наложить ограничения от длины входа, тогда для нее существует полиномиальный алгоритм. В качестве иллюстрации рассмотрим индивидуальную задачу РАЗБИЕНИЕ.
Процесс решения этой задачи удобно представлять в виде заполнения таблицы t (i, j ), где i = 1,, n, j = 0,, ∑ s(a i ); элементы таблицы
2
1
a i ∈A
могут принимать только два значения {F , T}. Пусть t (i, j ) = T означает
истинность утверждения «существует такое подмножество множества {a1 ,, a i }, что сумма размеров его элементов в точности равна j ».
Задача решается путем заполнения таблицы последовательно строчка
за строчкой.
Опишем работу алгоритма.
Определим элементы первой строки по следующему правилу:
t (1, j ) = T , когда либо j = 0, либо j = s (a1 );

t (1, j ) = F , в противном случае.
Каждая следующая строка заполняется с использованием значений, расположенных в предыдущей строке.
Строка i = 2,, n заполняется по правилу:
t (i, j ) = T , если t (i − 1, j − s(a i )) = T или t (i − 1, j ) = T ;

t (i, j ) = F , в противном случае.
После того как вся таблица будет заполнена, рассматриваемая
индивидуальная задача будет решена, поскольку ей соответствует ответ «да» тогда и только тогда, когда t (n, B) = T , где B = ∑ s(a i ).
2
1
a i ∈A
Проиллюстрируем работу построенного алгоритма на простом
примере. Пусть задано множество A = {a i , i = 1,,5} со следующими весами s(a1 ) = 1, s(a 2 ) = 4, s(a 3 ) = 2, s(a 4 ) = 3, s(a 5 ) = 6. Данной задаче соответствует ответ «да», поскольку s(a1 ) + s(a 2 ) + s(a 4 ) = s(a 3 ) + s(a 5 ). Действительно t (5,8) = T.
Решение индивидуальной задачи РАЗБИЕНИЕ
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
j
i
0
1
2
3
4
5
6
7
8
1
2
3
4
5
T
T
T
T
T
T
T
T
T
T
F
F
T
T
T
F
F
T
T
T
F
T
T
T
T
F
T
T
T
T
F
F
T
T
T
F
F
T
T
T
F
F
F
T
T
Время работы этого алгоритма ограничено полиномом от nB.
Может показаться, что это дает полиномиальный алгоритм решения
задачи РАЗБИЕНИЕ (и, следовательно, P=NP), но это неверно. Длина
l ( z) записи индивидуальной задачи РАЗБИЕНИЕ может быть представлена на входе словом длины O(n log 2 B) . Это следует из того факта, что каждое целое число s (a i ) может быть представлено на входе
словом длины O(log 2 s(a i )) . Но nB не ограничена никаким полиномом l ( z). Следовательно, построенный алгоритм не позволяет решить
задачу РАЗБИЕНИЕ за полиномиальное время.
Сформулируем несколько определений, они окажутся полезными
для понимания материала, обсуждаемого ниже.
Обозначим через m(z) - максимум модулей целых чисел, характеризующих задачу z.
Задачу Z принято называть задачей с числовыми параметрами,
если не существует такой полиномиальной функции p, которой
m( z) ≤ p(l ( z)) при любой z ∈ Z. Среди сформулированных выше задачами с числовыми параметрами являются задачи РАЗБИЕНИЕ,
КОММИВОЯЖЕР, О МИНИМАЛЬНОМ ОСТОВЕ.
Алгоритм A, решающий задачу с числовыми параметрами Z, называется алгоритмом с псевдополиномиальной временной сложностью (короче - псевдополиномиальным алгоритмом), если существует
такой полином p, что для любой индивидуальной задачи z ∈ Z время
TA ( z) решения задачи z удовлетворяет неравенству
TA ( z) ≤ p(l ( z), m( z)).
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сама задача Z в этом случае называется псевдополиномиально
разрешимой. Классическим примером NP-полной псевдополиномиально разрешимой задачи служит задача РАЗБИЕНИЕ.
Наличие такого алгоритма для задачи означает, что ее NPполнота в значительной степени зависит от того обстоятельства, что
на входе могут присутствовать чрезвычайно большие числа. Если бы
на величину таких чисел заранее было наложено какое-либо ограничение, например в виде полинома от длины входа, то время выполнения псевдополиномиального алгоритма для таких задач тоже ограничено полиномом. Естественно ожидать, что подобное ограничение
выполнено во многих задачах, встречающихся на практике. Легко заметить, что любой полиномиальный алгоритм является также псевдополиномиальным, поскольку время его работы ограничено полиномом от одного аргумента l (z).
Более того, алгоритм с псевдополиномиальным временем работы
может быть полезен даже в тех случаях, когда нельзя надеяться на естественное ограничение величины входных чисел. Такие алгоритмы
будут работать "экспоненциально долго" только для тех индивидуальных задач, в которых имеются "экспоненциально большие" числа.
Однако может оказаться, что подобные индивидуальные задачи
встречаются на практике редко. Если это так, то алгоритм этого типа
может служить почти столь же хорошо, как и алгоритм с полиномиальной временной сложностью, т.е. являться достаточно эффективным в реальных ситуациях. Таким образом, вопрос отыскания псевдополиномиального алгоритма для решения NP-полной задачи с
числовыми параметрами вовсе не является второстепенным при исследовании задачи.
Когда о массовой задаче известно, что она является NP-полной,
целесообразно исследовать какое-либо ее сужение.
Представление о подзадачах формализуется следующим определением. Для произвольной задачи распознавания Z и полинома p (с
целыми коэффициентами) обозначим через Zp подзадачу, получаемую
из Z рассмотрением только тех индивидуальных задач, для которых
выполнено соотношение m( z) ≤ p(l ( z)).
Легко заметить, что если задача Z принадлежит классу P, то любая ее подзадача Zp также входит в класс P. Но если Z является
NP-полной, ее подзадачи могут быть как NP-полными, так и полиномиально разрешимыми.
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Отметим, что если задача Z разрешима с помощью псевдополиномиального алгоритма, то Zp должна быть разрешима с помощью
полиномиального алгоритма.
Задачу Z будем называть NP-полной в сильном смысле, если Z
принадлежит классу NP и существует такой полином p (с целыми коэффициентами), что задача Zp является NP-полной. Если Z — NPполная в сильном смысле задача, то она не может быть решена псевдополиномиальным алгоритмом.
Многие из уже рассмотренных NP-полных задач обладают тем
свойством, что величина m( z) ограничена полиномом от длины задачи l ( z). Поэтому для этих задач нет различия между NP-полнотой и
NP-полнотой в сильном смысле. Примерами таких задач могут служить задачи ВЫПОЛНИМОСТЬ и ГАМИЛЬТОНОВ ЦИКЛ.
Наиболее простой путь доказательства сильной NP-полноты задачи с числовыми параметрами Z заключается в доказательстве NPполноты некоторой конкретной подзадачи Zp В качестве примера
приведем анализ задачи ЗКР.
Теорема. Задача ЗКР (задача КОММИВОЯЖЕРА в форме задачи
распознавания) является NP-полной в сильном смысле.
Доказательство. Рассмотрим подзадачу Zp задачи ЗКР, где p является константой, равной двум, т.е. m( z) ≤ 2, следовательно, расстояние между любыми двумя пунктами не превосходит двух.
Легко видеть, что рассматриваемая задача входит в класс NP.
Оракулу достаточно подсказать лишь маршрут движения коммивояжера и за полиномиальное время проверить, что длина маршрута
не превосходит заданного числа Q.
Задача ГАМИЛЬТОНОВ ЦИКЛ является частным случаем задачи ЗКР. Для иллюстрации данного факта по данному графу G = (V, E )
построим индивидуальную задачу ЗКР с V пунктами, положив расстояние между пунктами vi и v j равным 1, если (vi , v j )∈ E , и 2 в противном случае. Положим Q равным V . Очевидно, что обход длины Q
существует тогда и только тогда, когда в G = (V, E ) существует гамильтонов цикл. Теорема доказана.
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8. Несколько упражнений
В этом пункте сформулируем несколько утверждений, которые
полезно доказать самостоятельно для закрепления изложенного материала.
Докажите, что следующие задачи распознавания принадлежат
классу P, т.е. для каждой из них существует полиномиальный алгоритм.
• КУБ ЧИСЛА. Дано натуральное число. Требуется выяснить, является ли оно кубом некоторого другого натурального числа.
• СВЯЗНОСТЬ ГРАФА. Дан граф G = (V, E ) . Требуется выяснить,
является ли он связным.
• 2-ВЫПОЛНИМОСТЬ. Дан набор дизъюнкций, каждая из которых состоит из двух литералов. Требуется выяснить, является ли он
выполнимым.
Докажите, что следующие задачи распознавания принадлежат
классу NP.
• ИЗОМОРФИЗМ ПОДГРАФУ. Даны два графа G1 = (V1 , E1 ) и
G 2 = (V2 , E 2 ) . Требуется выяснить, содержит ли граф G1 подграф, изоморфный графу G2 . Иначе говоря, существуют ли подмножества
V ⊆ V1 и E ⊆ E1 , такие, что V = V2 , E = E2 , и такая взаимно однозначная
функция f : V2 → V, что {u, v} ∈ E2 тогда и только тогда, когда
{ f (u ), f (v)} ∈ E.
• ОРИЕНТИРОВАННЫЙ ГАМИЛЬТОНОВ ЦИКЛ. Дан ориентированный граф G = (V, A) . Требуется выяснить, содержит ли граф G
ориентированный гамильтонов цикл.
• МАКСИМАЛЬНЫЙ РАЗРЕЗ. Даны натуральное число K и
граф G = (V, E ), для каждого ребра e ∈ E определен вес w(e) ≥ 0 . Требуется выяснить, существует ли разбиение множества V на два таких непересекающихся множества V1 и V2 , что сумма весов ребер из E , соединяющих вершины из множеств V1 и V2 , не менее K.
• КВАДРАТНЫЕ СРАВНЕНИЯ. Даны натуральные числа a , b и
c . Требуется выяснить, существует ли натуральное число x < c, такое,
что x2 ≡ a (mod b).
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
• ПОКРЫТИЕ МАТРИЦЫ. Даны матрица A = {a ij } размером n × n с
целыми элементами и целое число K . Требуется выяснить, существует ли такое отображение f : {1,, n} → {−1,+1}, что ∑ a ij f (i) f ( j ) ≥ K.
1≤i , j ≤ n
Установите полиномиальное сведение задачи А к задаче В для
следующих задач.
• А - задача РАЗБИЕНИЕ, В - задача РЮКЗАК. (Формулировка
задачи РЮКЗАК: имеется набор {( pi , qi ) : i = 1,..., n} пар натуральных
чисел и заданы два натуральных числа P , Q. Требуется выяснить, существует ли такое множество I , для которого выполняются условия:
∑ pi ≤P и ∑ qi ≥Q ).
i∈I
i∈I
• А – задача ТРЕХМЕРНОЕ СОЧЕТАНИЕ, В – задача о ТОЧНОМ ПОКРЫТИИ ТРЕХЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ, ее
формулировка: даны конечное множество U и некоторый набор W
его трехэлементных подмножеств; требуется выяснить, существует
ли такой набор V попарно не пересекающихся подмножеств из W,
объединение которых совпадает с U.
• А – задача ГАМИЛЬТОНОВ ЦИКЛ, В – задача ОСТОВНОЕ
ДЕРЕВО ОГРАНИЧЕНОЙ СТЕПЕНИ, ее формулировка: даны граф
G = (V, E ) и натуральное число К; требуется выяснить, содержит ли
граф G такое остовное дерево, степень каждой вершины которого не
превосходит K.
• А – задача РАЗБИЕНИЕ, В – задача РАСПИСАНИЕ ДЛЯ
МУЛЬТИПРОЦЕССОРНОЙ СИСТЕМЫ, ее формулировка: даны два
натуральных числа m и D, конечное множество A и для каждого элемента a ∈ A определен вес s (a ) ≥ 0; требуется выяснить, существует ли разбиение множества A на m непересекающихся множеств


A = A1  A2  Am , такое, что max  ∑ s (a ) : i = 1,, m ≤ D.
 a∈ A

i
Попытаемся разглядеть практический смысл затронутых в методических указаниях понятий. Представим себя в роли разработчика
алгоритмов, перед которым поставлена новая дискретная задача. Каковы наши действия? Прежде всего, пороемся в собственной памяти,
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
рассчитывая припомнить что-нибудь подобное, потом - в библиотеке.
Если эти поиски закончатся неудачей (ситуация стандартная!), мы
вынуждены будем попытаться придумать эффективный (т.е. полиномиальный) алгоритм. Обладая неограниченной целеустремленностью
и будучи не слишком ленивыми, мы можем как угодно долго пребывать в состоянии поиска такого алгоритма. Но благоразумие и знакомство с изложенными в этих методических указаниях фактами
подскажут иной путь. В случае, когда определенные усилия не приводят к полиномиальному алгоритму, следует попытаться доказать
NP-полноту нашей задачи. И если это удастся сделать, надо прекратить все попытки искать полиномиальный алгоритм по причине их
безнадежности.
Правда, остается вопрос: а так ли уж сложны эти самые сложные
в NP задачи. Неформально величина сложности NP-полных задач
оценивается совокупными умственными затратами многочисленных
математиков, безуспешно пытавшихся в течение многих лет до появления теории NP-полных задач конструировать для таких задач полиномиальные алгоритмы. В формальной постановке речь идет о соотношении классов P и NP. Что на самом деле верно: неравенство
NP ≠ P или все-таки равенство между этими классами? Большинство
специалистов склоняются к первому варианту, но в целом вопрос остается открытым и привлекающим значительное внимание исследователей. Аргументированный ответ на этот вопрос явился бы выдающимся математическим результатом.
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Литература
1. Кук С.А. Сложность процедур вывода теорем // Кибернетический сборник (новая серия). 1975. Вып. 12. С. 5 – 15.
2. Карп Р.М. Сводимость комбинаторных проблем // Там же.
С. 16 - 38.
3. Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. 1973. Т. 9, № 3. С. 115 - 116.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация.
Алгоритмы и сложность. М.: Мир, 1985. 509 с.
Содержание
1. Примеры дискретных задач .............................................................. 3
2. Алгоритмы............................................................................................. 4
3. Полиномиальная разрешимость....................................................... 5
4. Алгоритмы с оракулом и класс NP .................................................. 8
5. Сравнение задач по сложности ......................................................... 9
6. Задачи, самые сложные в классе NP .............................................. 10
7. Задачи с числовыми параметрами и сильная NP-полнота ....... 15
8. Несколько упражнений ..................................................................... 19
Литература............................................................................................... 22
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
О сложности дискретных задач
Составители: Бондаренко Владимир Александрович
Краснов Михаил Владимирович
Редактор, корректор В.Н. Чулкова
Компьютерная верстка И.Н. Ивановой
Подписано в печать 17.03.2004 г. Формат 60×84/16.
Бумага тип. Усл. печ. л. 1,4. Уч.-изд. л. 1,0.
Тираж 80 экз. Заказ
.
Оригинал-макет подготовлен
в редакционно-издательском отделе Яргу.
Отпечатано на ризографе
Ярославский государственный университет.
150000, Ярославль, ул. Советская, 14.
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
О сложности
дискретных задач
25
Документ
Категория
Без категории
Просмотров
58
Размер файла
300 Кб
Теги
дискретное, сложности, задачи
1/--страниц
Пожаловаться на содержимое документа