Труднорешаемые и NP-полные задачи

Алгоритм называется полиномиальным (или имеющим полиномиальную временную сложность), если его временная сложность f(n) равна: O(p(n)) для некоторого полинома p(n). Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.

Попытки найти алгоритмы полиномиальной сложности для решения некоторых задач привели к понятию недетерминированной машины Тьюринга для (НДМТ) распознавания свойств, полученной из обычной машины Тьюринга заменой конечного состояния q₀ на два заключительных состояния – q_Y и q_N . Машина проверяет, удовлетворяют ли входные данные заданному свойству. Если она заканчивает работу в состоянии q_Y , то получен ответ «да», если заканчивает в состоянии q_N , то получен ответ «нет». Недетерминированная машина Тьюринга, помимо головки чтения/записи имеет дополнительное устройство, которое называется угадывающем модулем. Этот модуль может только записывать на ленту. Угадывающий модуль дает информацию для записи «догадки».

Программа для НДМТ (НДМТ-программа) определяется как и для машины Тьюринга в виде частичной функции p: Q x A ® Q x A x {L,S,R}. Вычисление на НДМТ в отличии от вычисления на машине Тьюринга имеет две различные стадии.

На первой стадии происходит «угадывание». В начальный момент времени входное слово w записывается в ячейках с номерами 1, 2, …, |w|, головка чтения/записи смотрит на ячейку 0, пишущая головка угадывающего модуля смотрит на ячейку с номером –1. Угадывающий модуль начинает управлять угадывающей головкой, которая делает один шаг в каждый момент времени и либо пишет в находящейся под ней ячейке одну из букв алфавита A и сдвигается влево, либо останавливается. В последнем случае угадывающий модуль заканчивает работу и начинает работать программа p.

Начиная с этого момента, вычисление НДМТ-программы осуществляется по тем же правилам, что и вычисление на машине Тьюринга. Вычисление заканчивается тогда, когда управляющее устройство перейдет в одно из заключительных состояний (q_Y и q_N); оно называется принимающим вычислением, если остановка происходит в состоянии q_Y . Остальные вычисления, в том числе не заканчивающиеся, называются непринимающими.

Любая НДМТ-программа p может иметь бесконечное число возможных вычислений при данном входе w, по одному для каждого слова-догадки из A*. Будем говорить, что НДМТ-программа p принимает w, если по крайней мере одно из ее вычислений, имеющих w на входе, является принимающим. Язык, распознаваемый программой p, - это язык L_p = {w Î A* : p принимает w}. Временем, требующимся НДМТ-программе p для того, чтобы принять слово w Î L_p , называется минимальное число шагов, выполняемых на стадии угадывания и проверки до момента достижения заключительного состояния q_Y , где минимум берется по всем принимающим вычислениям программы p на входе w. Временной сложностью НДМТ-программы p называется функция T_p : N⁺® N⁺, где N⁺ = {1, 2, 3, …}, определенная как T_p (n) = max {{1}È{m: существует w Î L_p , |w| = n, такое что время принятия w программой p равно m}}.

Если существует такой полином p(n) , что T_p (n) £ p(n) для всех n ³ 1, то НДМТ-программа называется имеющей полиномиальное время работы.

Класс NP – это класс (не обязательно всех) задач распознавания свойств (т.е. задач, решениями которых могут быть либо «да», либо «нет»), которые могут быть решены с помощью НДМТ-программы с полиномиальным временем работы. Большинство практически важных задач, для которых в настоящее время не известны полиномиальные алгоритмы, после переформулировки их в виде задач распознавания свойств, попадают в этот класс.

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