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

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

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

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

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

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

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

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

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

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