Теория сложности вычислений и сложностные классы задач

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?

Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач.

1) Класс P (задачи с полиномиальной сложностью)

Задача называется полиномиальной, т.е. относится к классу P, если существует константа k и алгоритм, решающий задачу с:

F_a(n)=O(n^k),

где n - длина входа алгоритма в битах n = |D| [6].

Задачи класса P - это интуитивно, задачи, решаемые за реальное время. Отметим следующие преимущества алгоритмов из этого класса:

· для большинства задач из класса P константа k меньше 6;

· класс P инвариантен по модели вычислений (для широкого класса моделей);

· класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином).

Таким образом, задачи класса P есть уточнение определения «практически разрешимой» задачи.

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

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

Рассмотрим, например задачу о сумме: Давно N чисел - А = (a₁,…a_n) и число V. Задача: Найти вектор (массив) X=(x₁,…,x_n), x_i{0,1}, такой, что a_ix_i = V.

Содержательно: может ли быть представлено число V в виде суммы каких либо элементов массива А. Если какой-то алгоритм выдает результат - массив X, то проверка правильности этого результата может быть выполнена с полиномиальной сложностью: проверка a_ix_i = V требует не более (N) операций.

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

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

3 ПРОБЛЕМА P = NP

После введения в теорию алгоритмов понятий сложностных классов Эдмондсом (Edmonds, 1965) была поставлена основная проблема теории сложности:

P = NP?

Словесная формулировка проблемы имеет вид: можно ли все задачи, решение которых проверяется с полиномиальной сложностью, решить за полиномиальное время? [6]

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

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

Рисунок 6.1 - Соотношение классов P и NP

4 КЛАСС NPC (NP - ПОЛНЫЕ ЗАДАЧИ)

Понятие NP - полноты было введено независимо Куком (Stephen Cook, 1971) и Левиным (журнал «Проблемы передачи информации», 1973,т.9, вып. 3) и основывается на понятии сводимости одной задачи к другой [6].

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

Таким образом, если задача 1 задана множеством конкретных проблем D_A1, а задача 2 - множеством, и существует функция f_s (алгоритм), сводящая конкретную постановку задачи 2 (d_А2) к конкретной постановке задачи 1(d_А1): f_s(d₍₂₎D_A2) = d₍₁₎D_A1, то задача 2 сводима к задаче 1.

Если при этом F_A (f_s) = O(n^k), т.е. алгоритм сведения принадлежит классу P, то говорят, что задача 1 полиномиально сводится к задаче 2 [6].

Принято говорить, что задача задается некоторым языком, тогда если задача 1 задана языком L1, а задача 2 - языком L2, то полиномиальная сводимость обозначается следующим образом: L2 _p L1.

Определение класса NPC (NP-complete) или класса NP-полных задач требует выполнения следующих двух условий: во-первых, задача должна принадлежать классу NP (L NP), и, во-вторых, к ней полиномиально должны сводиться все задачи из класса NP (L_{x P} L, для каждого L_x NP), что схематично представлено на рис 6.2.

Рисунок 6.2 - Сводимость и класс и NPC

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

Схема доказательства состоит в сведении любой задачи из NP к данной задаче из класса NPC с полиномиальной трудоемкостью и решении этой задачи за полиномиальное время (по условию теоремы).

В настоящее время доказано существование сотен NP- полных задач [6,7], но ни для одной из них пока не удалось найти полиномиального алгоритма решения. В настоящее время исследователи предполагают следующее соотношение классов, показанное на рис 6.3 - P NP, то есть NP \ P , и задачи из класса NPC не могут быть решены (сегодня) с полиномиальной трудоемкостью.

Рисунок 6.3 - Соотношение классов P, NP, NPC

5 ПРИМЕРЫ NP - ПОЛНЫХ ЗАДАЧ