Сложностные классы задач

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

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

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

Задача называется полиномиальной, т.е. относится к классу P, если существует константа k и алгоритм, решающий задачу с F_a(n)=O(n^k), где n - длина входа алгоритма в битах n = |D|

Задачи класса P – это интуитивно, задачи, решаемые за реальное время.

Отметим следующие преимущества алгоритмов из этого класса:

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

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

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

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

Дано N чисел – А = (a₁,…a_n) и число V.

Содержательно: может ли быть представлено число V в виде суммы каких-либо элементов массива А.

Если какой-то алгоритм выдает результат – массив X, то проверка правильности этого результата может быть выполнена с полиномиальной сложностью: проверка \(\sum{aixi}\) = V требует не более Q (N) операций.

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

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

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

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

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

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

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