Труднорешаемые и NP-полные задачи
Алгоритм называется полиномиальным (или имеющим полиномиальную временную сложность), если его временная сложность f(n) равна: O(p(n)) для некоторого полинома p(n). Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.
Попытки найти алгоритмы полиномиальной сложности для решения некоторых задач привели к понятию недетерминированной машины Тьюринга для (НДМТ) распознавания свойств, полученной из обычной машины Тьюринга заменой конечного состояния q0 на два заключительных состояния – qY и qN . Машина проверяет, удовлетворяют ли входные данные заданному свойству. Если она заканчивает работу в состоянии qY , то получен ответ «да», если заканчивает в состоянии qN , то получен ответ «нет». Недетерминированная машина Тьюринга, помимо головки чтения/записи имеет дополнительное устройство, которое называется угадывающем модулем. Этот модуль может только записывать на ленту. Угадывающий модуль дает информацию для записи «догадки».
Программа для НДМТ (НДМТ-программа) определяется как и для машины Тьюринга в виде частичной функции p: Q x A ® Q x A x {L,S,R}. Вычисление на НДМТ в отличии от вычисления на машине Тьюринга имеет две различные стадии.
На первой стадии происходит «угадывание». В начальный момент времени входное слово w записывается в ячейках с номерами 1, 2, …, |w|, головка чтения/записи смотрит на ячейку 0, пишущая головка угадывающего модуля смотрит на ячейку с номером –1. Угадывающий модуль начинает управлять угадывающей головкой, которая делает один шаг в каждый момент времени и либо пишет в находящейся под ней ячейке одну из букв алфавита A и сдвигается влево, либо останавливается. В последнем случае угадывающий модуль заканчивает работу и начинает работать программа p.
Начиная с этого момента, вычисление НДМТ-программы осуществляется по тем же правилам, что и вычисление на машине Тьюринга. Вычисление заканчивается тогда, когда управляющее устройство перейдет в одно из заключительных состояний (qY и qN); оно называется принимающим вычислением, если остановка происходит в состоянии qY . Остальные вычисления, в том числе не заканчивающиеся, называются непринимающими.
Любая НДМТ-программа p может иметь бесконечное число возможных вычислений при данном входе w, по одному для каждого слова-догадки из A*. Будем говорить, что НДМТ-программа p принимает w, если по крайней мере одно из ее вычислений, имеющих w на входе, является принимающим. Язык, распознаваемый программой p, - это язык Lp = {w Î A* : p принимает w}. Временем, требующимся НДМТ-программе p для того, чтобы принять слово w Î Lp , называется минимальное число шагов, выполняемых на стадии угадывания и проверки до момента достижения заключительного состояния qY , где минимум берется по всем принимающим вычислениям программы p на входе w. Временной сложностью НДМТ-программы p называется функция Tp : N+® N+, где N+ = {1, 2, 3, …}, определенная как Tp (n) = max {{1}È{m: существует w Î Lp , |w| = n, такое что время принятия w программой p равно m}}.
Если существует такой полином p(n) , что Tp (n) £ p(n) для всех n ³ 1, то НДМТ-программа называется имеющей полиномиальное время работы.
Класс NP – это класс (не обязательно всех) задач распознавания свойств (т.е. задач, решениями которых могут быть либо «да», либо «нет»), которые могут быть решены с помощью НДМТ-программы с полиномиальным временем работы. Большинство практически важных задач, для которых в настоящее время не известны полиномиальные алгоритмы, после переформулировки их в виде задач распознавания свойств, попадают в этот класс.
Задача из NP называется NP-полной, если всякая другая задача из класса NP может быть сведена к ней за полиномиальное время. Таким образом, если для некоторой NP-полной задачи существует полиномиальный алгоритм, то и любая задача из класса NP полиномиальна разрешима, а если какая-то задача из NP труднорешаемая, то и любая NP-полная задача является труднорешаемой.
6. Модальная и темпоральная логикИ................................................................................................................ 49
6.1. Синтаксис модальной логики......................................................................................................................................... 49
6.2. Семантика модальной логики......................................................................................................................................... 50
6.3. Алгоритмическая логика Хоара..................................................................................................................................... 53
6.4. Системы Гильберта......................................................................................................................................................... 55
6.5. Темпоральная логика...................................................................................................................................................... 61
7. АЛГОРИТМЫ И РЕКУРСИВНЫЕ ФУНКЦИИ............................................................................................................... 63
7.1. Частично рекурсивные функции..................................................................................................................................... 64
7.2. Машины Тьюринга.......................................................................................................................................................... 67
7.3. Вычислительная сложность............................................................................................................................................ 69