Классы 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)).

Дата добавления: 2015-07-11