2. Основные понятия NP-полноты

Рассмотрим класс Задач распознавания свойств как множество проблем, решением которых является ответ «Да» или «Нет».

Оптимизационной задаче

Max{F(X): XÎS}

Соответствует задача распознавания свойств: «Существует ли решение XÎS, значение функционала на котором F(X)³ K?», где K – наперед заданное число.

Например, оптимизационной задаче коммивояжера (КМ) соответствует следующая задача распознавания свойств.

Задан список городов N, расстояния между городами (Cij), а также число B. Спрашивается существует ли обход городов длины не более B?

Под Общей задачей (проблемой) P будем понимать некоторый общий вопрос, требующий ответа. Если все параметры общей задачи имеют конкретные значения, то такую задачу будем называть Индивидуальной.

Определение 2.1. Количество символов в стандартном (двоичном) представлении данных индивидуальной задачи XÎP назовем Входной длиной (или Длиной записи исходной информации) и обозначим L=L(X).

Определение 2.2. Пусть алгоритм A решает проблему P и TA(X) количество элементарных операций выполняемых алгоритмом A при решении индивидуальной задачи XÎP. Тогда величина

Называется Трудоемкостью алгоритма A.

Определение 2.3. Алгоритм A решения проблемы P называется Полиномиальным, если

При некотором положительном целом D.

Алгоритмы, трудоемкость которых не ограничена полиномом от входной длины, называются Экспоненциальными.

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

Пример 2.1. Предположим алгоритм A1 решает задачу с полиномиальной трудоемкостью O(N5), а алгоритм A2 имеет экспоненциальную трудоемкость O(2N), где N – входная длина. Пусть оба алгоритма реализуются на компьютере, который выполняет 1 миллион операций в секунду. Тогда при N=60 алгоритм A1 будет работать 13 минут, а для завершения работы алгоритма A2 потребуется 366 столетий.

Более того, прогресс в создании быстродействующих компьютеров не решит эту проблему. Предположим, что алгоритм A2 работает на вышеупомянутом компьютере 1 час для решения задачи размерности N. Если взять компьютер, который выполняет в 1000 раз больше операций, т. е. 1 миллиард операций в секунду, то размерность задачи, которая решается на таком компьютере в течение 1 часа будет всего N + 9.97.

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

Определение 2.4. NP – это класс задач Распознавания свойств, обладающих свойством, что Проверка ответа «Да» для заданного решения осуществляется за полиномиальное время.

Заметим, что задачи рапознавания свойств, соответствующие рассмотренным выше оптимизационным задачам, принадлежат классу NP.

Определение 2.5. P – это класс задач из NP, для которых существует полиномиальный алгоритм их решения.

Определение 2.6. Пусть задачи P И Q обе из класса NP. Если любая индивидуальная задача P может быть преобразована как индивидуальная задача Q за полиномиальное число операций, то P Полиномиально сводится к Q.

Определение 2.7. Класс NP-Полных проблем (обозначим его NPC) – это подмножество задач PÎNP, обладающих свойством, что любая задача QÎNP Полиномиально сводится к P.

Проблемы из NPC принято считать самыми сложными, для которых не существует полиномиальных алгоритмов их решения. Оказывается таких проблем много. Первой же задачей, NP-полнота которой была доказана Куком С. А. в 1970 г., является задача ВЫПОЛНИМОСТЬ, одна из кратких формулировок которой приведена ниже.

ВЫПОЛНИМОСТЬ. Задано множество N={1,...,N}, и 2M его подмножеств {CI}I=1,...,M и {Di}I=1,...,M. Существует ли булевый вектор XÎBn, удовлетворяющий всем неравенствам

Лемма 2.1. Пусть задачи P,QÎNP.

1) Если QÎP и P полиномиально сводится к Q, то PÎP.

2) Если PÎNPC и P полиномиально сводится к Q, то QÎNPC.

Доказательство. Утверждение 1) очевидно. Докажем 2). Возьмем некоторую задачу RÎNP. Так как PÎNPC, то R полиномиально сводится к P. Однако P полиномиально сводится к Q, и, следовательно, R полиномиально сводится к Q. Так как это имеет место для всех RÎNP, значит QÎNPC.¨

Следствие. Если NÇPC¹Æ, тогда P=NP.

Доказательство. Предположим QÎPÇNPC. Пусть RÎNP. По утверждению 2) Леммы 2.1, если RÎNP и QÎNPC, то R полиномиально сводится к Q. Согласно утверждению 1) Леммы 2.1, так как QÎP и R полиномиально сводится к Q, то RÎP. Значит NPÍP и, следовательно, P=NP.¨

Лемма 2.1 дает простой способ доказательства NP-полноты задач. Для доказательства принадлежности задачи PÎNP классу NPC достаточно взять какую-нибудь задачу QÎNPC и свести ее к задаче P за полиномиальное время.

Пример 2.2. Простой цикл, содержащий все вершины графа, называется Гамильтоновым. Проблема ГАМИЛЬТОНОВ ЦИКЛ (ГЦ) формулируется следующим образом.

Задан граф G=(V,E). Спрашивается содержит ли G гамильтонов цикл?

Известно, что ГЦÎNPC. Покажем, что задача коммивояжера также NP-полна, сведя к ней задачу ГЦ. Для этого по заданному графу G=(V,E), |V|=M построим задачу КМ, положив множество городов N=V, расстояния от I до J равным Cij=1, если (I,J)ÎE и Cij=2, если (I,J)ÏE и B=M. Очевидно, данное сведение полиномиально.

Отсюда можно сделать вывод, что если задача КМ полиномиально разрешима, то и ГЦÎP. И, наоборот, если для ГЦ не существует полиномиального алгоритма, то и КМ не разрешима за полином.

Проблема доказательства, что P=NP или P¹NP является основной в теории NP-полноты. Для многих задач показано, что они лежат Либо в классе P, Либо в NPC. До сих пор никому не удалось доказать ни равенства P=NP, ни неравенства P¹NP. Однако большое количество NP-полных задач, для которых не найдено полиномиальных алгоритмов, оправдывает существующую на настоящий момент гиппотезу, что P¹NP.

Определение 2.8. Оптимизационная (экстремальная) задача, для которой соответствующая ей задача распознавания свойств NP-полна, называется NP-Трудной.

Рассмотрим NP-полную проблему

РАЗБИЕНИЕ. Задано множество A={A1,…,An}, каждый элемент которого имеет вес S(Ai)ÎZ+. Пусть B=S(A) четное.

Существует ли разбиение A на два подмножества одинакового веса, т. е. существует ли А¢Í А: S(A)= S(A)?

Введем функцию

T(I,J)=

Заметим, что значения функции T(I,J) вычисляются достаточно просто. Представим, что эти значения заносятся в таблицу (см. Таб. 2.1), строка которой соответствует I, а столбец – J. Тогда эта таблица заполняется строка за строкой, начиная с первой, по следующему правилу:

В первой строке T(1,J)=T тогда и только тогда, когда J=0, или J=S(A1);

В строках I=2,… N Значение T(I,J)=T для 0 £ J £ B/2, только в случаях, когда:

- либо T(i-1,j)=T,

- либо S(ai) £ j и T(i-1,j-s(ai))=T.

Пример 2.3. Пусть индивидуальная задача РАЗБИЕНИЕ задана множеством элементов A={A1,…,A5} с весами S(A1)=1, S(A2)=9, S(A3)=5, S(A4)=3, S(A5)=8. Вычислим B=26. В Таб. 2.1 изображены только значения T, пустые клетки соответствуют значению F.

J

0

1

2

3

4

5

6

7

8

9

10

11

12

13

I

1

T

T

2

T

T

T

T

3

T

T

T

T

T

T

4

T

T

T

T

T

T

T

T

T

T

T

5

T

T

T

T

T

T

T

T

T

T

T

T

Таб. 2.1.

Как видно из таблицы, T(5,13)=T. Значит, множество можно разбить на два подмножества одинакового веса. Это разбиение легко восстанавливается по таблице и соответствует А¢={A1, A2, A4}.

Нетрудно заметить, что трудоемкость решения задачи определяется размерностью таблицы и равна O(NB). То есть наряду с длиной входа, в оценке трудоемкости присутствует числовой параметр B.

Обозначим через N(X) максимальный числовой параметр индивидуальной задачи XÎP.

Определение 2.9. Алгоритм решения задачи P называется Псевдо-полиномиальным, если для любой индивидуальной задачи XÎP его трудоемкость ограничена полиномом от двух аргументов: входной длины L(X) и значения максимального числового параметра N(X).

Определение 2.10. Задачу P называют NP-полной (трудной) В сильном смысле, если для ее решения не существует псевдо-полиномиального алгоритма.

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

Теорема 2.1. Если P¹NP, то не существует полиномиального алгоритма A решения булевой задачи о ранце (ЗР):

	(2.1)
	(2.2)

С целочисленными Vk и Sk, который строит решение любой индивидуальной задачи IÎЗР с ограниченной константой абсолютной погрешностью, т. е.

|A(I) – OPT(I)|£ Q = const,

(2.3)

Где A(I) – значение функционала (2.1) на решении, постороенном алгоритмом A, а OPT(I) – оптимальное значение функционала для задачи I.

Доказательство. Предположим противное: существует такой полиномиальный алгоритм A, что |A(I) – OPT(I)|£ Q и Q>0, целое. Покажем, что тогда алгоритм А можно использован для построения оптимального решения ЗР, которая NP-трудна, что противоречит условию P¹NP.

Каждую индивидуальную задачу I можно свести к задаче I¢ заменой параметров Vk на (Q+1)Vk. Применим алгоритм A к задаче I¢. Очевидно, выполнение следующих двух свойств:

· А(I¢) кратно (Q+1);

· OPT(I¢)=(Q+1)OPT(I).

Раз в предположении неравенство (2.3) выполняется для любой индивидуальной задачи, то

|А(I¢) – OPT(I¢)|£ Q.

Следовательно,

|А(I¢) – OPT(I¢)|=|А(I¢) – (Q+1)OPT(I)| £ Q.

Разделив обе части последнего неравенства на (Q+1), получим

| - OPT(I)| £<1.

Значит, в силу целочисленности величин,

- OPT(I) = 0,

Откуда

А(I¢) = (Q+1)OPT(I) = OPT(I¢),

Что противоречит NP-трудности задачи и предположению P¹NP.¨

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

< Предыдущая		Следующая >