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

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

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

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

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

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

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

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

  • класс P инвариантен по модели вычислений (для широкого класса моделей);
  • класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином).

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

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


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

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

Дано N чисел – А = (a1,…an) и число V.

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

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

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

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

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

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

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

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

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


2012-12-20 • Просмотров [ 1828 ]