9.Теория np-полноты

В конце 60-х и начале 70-х годов был внесен интересный вклад в теорию сложности, касающийся сравнения различных типов алгоритмов. Главная роль здесь принадлежит американскому математику С.А.Куку.

Три фундаментальных части предложенной Куком концепции заключаются в следующем.

1. Были введены определения двух классов задач. Один из них был связан с полиномиальными алгоритмами, а другой - с переборными.

2. Были введены понятия сводимости задач. Сводимость позволяла характеризовать принадлежность к определенному классу.

3. Для некоторой конкретной задачи было конструктивно доказано, что она в определенном смысле может рассматриваться, как самая сложная. (С помощью сводимости затем множество таких самых сложных задач было дополнено.)

9.1.Классы p и np.

Рассмотрим дискретную оптимизационную задачу Z в форме распознавания. Ей, как было выше описано, сопоставляется язык L_Z.

Класс P - это класс языков, допускаемых МТ за полиномиальное время. (То есть эта МТ, во-первых, допускает язык, а, во-вторых, время ее работы ограничено полиномом.)

Задачи (языки) из этого класса называют полиномиально разрешимыми.

В случае НМТ для одного и того же слова I, представляющего собой запись условия некоторой индивидуальной задачи, может существовать множество различных отгадок {U}. Зафиксируем слово I и рассмотрим все возможные вычисления НМТ на различных отгадках. На каждой из них обычная головка работает t_T(I,U) тактов.

Если хотя бы для одного такого вычисления НМТ за конечное число шагов остановится в конечном состоянии q_y ,то это вычисление называется принимающим, t_T(I,U) полагается равным числу тактов работы НМТ. В противном случае (НМТ зацикливается или останавливается в состоянии q_n) вычисление называется непринимающим.

В качестве меры трудоемкости решения задачи I в форме распознавания на НМТ рассматривается величина

где минимум берется по всем принимающим вычислениям.

Если для некоторой массовой задачи Z НМТ допускает ее индивидуальную задачу I тогда и только тогда, когда I имеет ответ "да", то говорят, что НМТ допускает язык L_Z .

Класс NP - это класс языков, допускаемых НМТ за полиномиальное время. (То есть эта НМТ, во-первых, допускает язык, а, во-вторых, время ее работы ограничено полиномом.)

Теорема. Если ZNP, то существует такой полином p, что Z может быть решена на детерминированной МТ за время O(2^p(n)).

Доказательство. Пусть T - НМТ, решающая Z за время q(n). То есть для каждого I найдется отгадка U(I) такая, что после ее записи НМТ работает уже как обычная МТ, а число тактов работы не превосходит q(n). Ясно, что число символов самой отгадки (ее нужно прочесть в процессе решения) не может превосходить q(n).

Пусть k - число символов в алфавите НМТ. Тогда всего нужно рассмотреть k^q(n) отгадок. Построим такую МТ, которая работает также, как обычная головка нашей НМТ, а на входной ленте у нее записаны все k^q(n) отгадок. Она поочередно просматривает отгадки. Если хотя бы на одной она останавливается в состоянии, то вычисление завершается. Временная сложность не превосходит q(n)k^q(n), что при надлежащем выборе полинома не превосходит O(2^p(n)).