2. Класс np (полиномиально проверяемые задачи)

Представим себе, что некоторый алгоритм получает решение некоторой задачи – соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность?

Рассмотрим, например задачу о сумме.

Дано N чисел – А=(а₁,…., а_п) и число V. Найти вектор (массив) Х=(х₁,…,х_п), х_i{0, 1}, такой, что a_i х_i=V. Может ли быть представлено число V в виде суммы каких-либо элементов массива ?

Если какой-то алгоритм выдает результат – массив Х, то проверка правильности этого результата может быть выполнена с полиномиальной сложностью: проверка a_i х_i=V требует не более Q(N) операций.

Формально DD_A, |D|=n поставим в соответствие сертификат SS_A, такой что и алгоритм A_s = A_s(D, S), такой, что |S|=O(n^l) он выдает «1», если решение верно, и «0», если решение неверно. Тогда задача принадлежит классу NP, если F(A_s)=O(n^m).

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

3. Проблема P = NP

После введения в теорию алгоритмов понятий сложностных классов Эдмондсом (1965) была поставлена основная проблема теории сложности – P = NP? Словесная формулировка проблемы имеет вид: можно ли все задачи, решение которых проверяется с полиномиальной сложностью, решить за полиномиальное время? Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть полиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи.

На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пусто (см. рис 9.1).

Рис. 9.1. Соотношение классов P и NP.

4. Класс npc (np – полные задачи)

Понятие NP – полноты было введено независимо Куком (1971) и Левиным (1973) и основывается на понятии сводимости одной задачи к другой.

Сводимость может быть представлена следующим образом: если мы имеем задачу 1 и решающий эту задачу алгоритм, выдающий правильный ответ для всех конкретных проблем, составляющих задачу, а для задачи 2 алгоритм решения неизвестен, то если мы можем переформулировать (свести) задачу 2 в терминах задачи 1, то мы решаем задачу 2.

Определение класса NPC (NP-complete) или класса NP-полных задач требует выполнения следующих двух условий: во-первых, задача должна принадлежать классу NP, и, во-вторых, к ней полиномиально должны сводиться все задачи из класса NP , что схематично представлено на рис 9.2.

Рис. 9.2. Сводимость NP к NPC.

Для класса NPC доказана следующая теорема: Если существует задача, принадлежащая классу NPC, для которой существует полиномиальный алгоритм решения (F=O(n^k)), то класс P совпадает с классом NP, т.е. P=NP.

В настоящее время доказано существование сотен NP–полных задач, но ни для одной из них пока не удалось найти полиномиального алгоритма решения. В настоящее время исследователи предполагают следующее соотношение классов, показанное на рис 9.3. – P ≠ NP, то есть NP \ P ≠ 0, и задачи из класса NPC не могут быть решены (сегодня) с полиномиальной трудоемкостью.

Рис. 9.3. Соотношение классов P, NP и NPC.