Детерминированные машины Тьюринга и класс Р
Детерминированная машина Тьюринга (ДМТ) состоит из управляющего устройства с конечным числом состояний, читающей/пишущей головки, которая может считывать и записывать символы в ячейки, и неограниченной в обе стороны ленты, разделенной на бесконечное число одинаковых ячеек, занумерованных целыми числами. ДМТ-программа определяется следующими компонентами:
— конечным множеством символов, которые записываются на ленте, подмножеством входных символов и выделенным пустым символом ;
— конечным множеством состояний , в котором выделены начальное состояние и два заключительных состояния: и ;
— функцией переходов
.
Работа ДМТ-программы определяется следующим образом. Входом для программы является слово , которое записывается в ячейки с номерами 1, 2, ..., |х| по одному символу в ячейку. Все остальные ячейки в начальный момент времени содержат символ . Программа начинает работу в состоянии а головка находится над ячейкой с номером 1.
Процесс вычислений осуществляется последовательно шаг за шагом.
Один шаг вычислений ДМТ-программы состоит из следующих действий:
— если текущее состояние есть или то процесс вычислений заканчивается с результатом соответственно «да» или «нет»;
— в противном случае головка считывает из ячейки некоторый символ вычисляет , записывает на место символ , переходит в состояние , сдвигает головку на одну ячейку вправо ( ) или влево ( ).
Пусть ‑ ДМТ-программа.
Определение 5.3. Говорят, что программа принимает слово , если ее применение ко входу приводит к остановке машины в состоянии .
Определение 5.4. Язык является распознаваемым программой , если составляющее его множество слов есть .
Определение 5.5. Программа называется алгоритмической, если она останавливается на всех словах входного алфавита независимо от того, принимает программа слова или нет.
Определение 5.6. Говорят, что ДМТ-программа решает задачу распознавания при кодировании , если она алгоритмическая и .
Временная сложность ДМТ-программы определяется следующим выражением:
существует такое слово , ,
что вычисление по программе для входа требует
шагов от начала до останова}.
Определение 5.7. Программа называется полиномиальной ДМТ-программой, если существует полином такой, что для любого :
.
Заметим, что алгоритмическая программа может не только решать задачи распознавания, но и вычислять значения функции . При этом значение функции для каждого входа определяется словом, записанным после останова машины в ячейках с номерами 1, 2, 3,..., включая последнюю непустую ячейку.
Теперь можно формально определить первый важный класс языков — класс .
Определение 5.8. Класс языков распознавания состоит из языков L, для которых принадлежность к нему определяется за полиномиальное время, т.е. = {L: существует полиномиальная ДМТ-программа для которой }. Будем говорить, что задача распознавания принадлежит классу при кодировании , если .
5.1.7. Недетерминированные машины Тьюринга и класс
Понятие «полиномиальной проверяемости» позволяет выделить важный класс задач . Задачи этого класса решаются недетерминированными алгоритмами за полиномиальное время.
Недетерминированные алгоритмы состоят из стадии угадывания и стадии проверки. На стадии угадывания индивидуальной задаче ставится в соответствие (угадывается) некоторая структура . Затем и вместе подаются в качестве входа на стадию проверки, которая выполняется обычным детерминированным образом и либо заканчивается получением ответа «да» или «нет», либо продолжается бесконечно.
Определение 5.9. Недетерминированный алгоритм решает задачу распознавания , если для любой индивидуальной задачи выполняются следующие условия:
1. Если , то существует такая структура , угадывание которой для входа приведет к тому, что стадия проверки, начиная работу на входе , закончится ответом «да»;
2. Если , то не существует такой структуры , угадывание которой для входа обеспечило бы окончание стадии проверки на входе с ответом «да».
Формальной моделью для недетерминированного алгоритма является программа для недетерминированной машины Тьюринга (НДМТ), которая отличается от ДМТ наличием угадывающего модуля с пишущей головкой.
Определение 5.10. Вычисление, которое осуществляет НДМТ-программа, называется принимающим, если остановка происходит в состоянии . Все остальные вычисления, независимо от того, заканчивает или нет работу соответствующая НДМТ, называются непринимающими.
Отметим, что НДМТ-программа может иметь бесконечное число возможных вычислений при данном входе , по одному для каждого слова, полученного на этапе угадывания.
Определение 5.11. Говорят, что НДМТ-программа принимает слово , если по крайней мере одно из вычислений при входе является принимающим.
Определение 5.12. Язык , распознаваемый НДМТ-программой , — это множество слов { | принимает }.
Время, требующееся для того, чтобы принять слово , ‑ это минимальное число шагов, выполняемых на стадиях угадывания и проверки, причем минимум берется по всем принимающим вычислениям для входа .
Временная сложность НДМТ-программы определяется следующим выражением:
существует такое слово , ,
что время принятия программой равно }).
Определение 5.13. НДМТ-программа называется полиномиальной (или программой с полиномиальным временем работы), если существует полином такой, что для любого имеет место неравенство .
Теперь можно формально определить второй важный класс языков ‑ класс . Он определяется следующим образом.
Определение 5.14. Класс языков распознавания = {L: существует полиномиальная НДМТ-программа для которой }. Будем говорить, что задача распознавания принадлежит классу при кодировании , если .
Как и в случае класса , говорим, что принадлежит классу , не упоминая конкретную схему кодирования, в том случае, когда возможно определить некоторую разумную схему кодирования задачи , которая даст язык, принадлежащий .
Учитывая замечание о полиномиальной эквивалентности существующих моделей вычислительных устройств, будем в дальнейшем отождествлять формально определенный класс с классом всех задач распознавания, «разрешимых» недетерминированными алгоритмами с полиномиальным временем работы.
5.2. Использование теории сложности в дискретной оптимизации 5.2.1. Соотношение между классами и
Всякий детерминированный полиномиальный алгоритм можно рассматривать как частный случай недетерминированного полиномиального алгоритма, в котором отсутствует стадия угадывания, а стадия проверки совпадает с детерминированным алгоритмом. Поэтому справедливо , т.е. . В настоящее время не удалось доказать ни одно из более сильных утверждений: или .
Один из результатов теории сложности сформулирован в следующей теореме.
Теорема 5.1. Если , то существует такой полином , что может быть решена детерминированным алгоритмом с временной сложностью .
5.2.2. Полиномиальная сводимость и -полные задачи
Центральное место в теории -полных задач занимает понятие полиномиальной сводимости.
Определение 5.15. Говорят, что имеет место полиномиальная сводимость языка к языку , если существует функция , удовлетворяющая двум условиям:
— существует ДМТ-программа, вычисляющая с временной сложностью, ограниченной некоторым полиномом;
— для любого , в том и только том случае, когда .
Если полиномиально сводится к , то будем писать и говорить « сводится к » (опуская слово «полиномиально»). Важность введенного понятия «полиномиальная сводимость» вытекает из следующей теоремы.
Теорема 5.2. Если , то из следует, что (эквивалентное утверждение: из следует, что ).
Доказательство. Достаточно рассмотреть в качестве ДМТ-программы, распознающей композицию двух полиномиальных ДМТ-программ. Первая из них вычисляет функцию , вторая распознает . Время работы полученной программы ограничено полиномом:
,
где , и ‑ полиномы, ограничивающие время работы ДМТ-программы, вычисляющей и распознающей соответственно ( , , .
Определение 5.16. Задача распознавания полиномиально сводится к задаче распознавания ( ), если . Таким образом, на уровне задач распознавания полиномиальная сводимость означает наличие функции , удовлетворяющей двум условиям:
— вычисляется полиномиальным алгоритмом;
— для всех , тогда и только тогда, когда .
Пример 5.1. Покажем сводимость задачи гамильтонов цикл (ГЦ) к задаче коммивояжера (ЗК).
Задача гамильтонов цикл заключается в следующем.
Условие. Задан неориентированный граф .
Вопрос. Верно ли, что содержит гамильтонов цикл (элементарный цикл, проходящий через все вершины графа)?
Рассмотрим индивидуальную ЗК, которая строится по конкретной индивидуальной задаче ГЦ: множество городов совпадает с множеством вершин, расстояние , если и , если . Границу для искомого маршрута положим равной . Построение индивидуальной задачи ЗК (обозначим ее через ) по существу сводится к вычислению расстояний, т. е. может быть осуществлено за полиномиальное от размерности индивидуальной задачи ГЦ (с параметром ) время.
Покажем, что G содержит гамильтонов цикл тогда и только тогда, когда в имеется проходящий через все города маршрут длины, не превосходящей . Пусть ‑ последовательность вершин графа, соответствующая гамильтонову циклу. Определим маршрут в той же последовательностью городов. Тогда длина этого маршрута, в соответствии с введенными расстояниями, равна , причем маршрут проходит через все города.
Определение 5.17. Язык называется -полным, если , и для любого другого языка следует, что (аналогично определяется -полная задача распознавания).
Теорема 5.3. Если , ‑ -полный язык, и , то также NP-полный язык.
Доказательство. Пусть ‑ любой язык из класса . Тогда из и транзитивности отношения « » следует, что .
Таким образом, для доказательства -полноты некоторой задачи распознавания достаточно показать, что некоторая известная -полная задача сводится к данной.
Теорема Кука
В соответствии с результатами, полученными в предыдущем параграфе, для исследования класса -полных задач необходимо получить хотя бы одну задачу, принадлежащую этому классу. В качестве такой задачи выступает известная задача выполнимости булевых формул (SAT).
Задача Выполнимость заключается в следующем.
Условие. Задано множество булевых переменных и набор дизъюнкций , где , a ‑ это либо либо ее отрицание .
Вопрос. Существует ли такой набор значений истинности на множестве X, что выполнима конъюнкция этих дизъюнкций ?[3]
Теорема 5.4 (Кук). Задача Выполнимость ‑ - полная задача.
Схема доказательства.
1. Очевидно, что за полиномиальное число шагов можно убедиться в том, является или нет выполняющим конкретный набор значений истинности на для . Выбор самого набора осуществляется недетерминированной процедурой. Таким образом, задача SAT лежит в классе .
2. Пусть задача SAT представлена некоторым языком для некоторой разумной схемы кодирования . Для доказательства -полноты задачи SAT необходимо показать, что для всех языков из класса справедливо: . Учитывая то, что любой язык из может быть представлен в стандартном виде, а именно НДМТ-программой, распознающей этот язык, достаточно показать, что имеет место полиномиальная сводимость языка, распознаваемого этой программой, к .
3. Формализуем процесс распознавания языка НДМТ-программой , задаваемой компонентами и имеющей временную сложность , ограниченную сверху полиномом . Условие равносильно одновременному выполнению шести условий, которые по сути задают работу машины Тьюринга:
1. В любой момент времени (т. е. после шага, проверяющего вычисления) программа находится ровно в одном состоянии;
2. В любой момент времени читающая/пишущая головка просматривает ровно одну ячейку;
3. В любой момент времени каждая ячейка содержит ровно один символ из ;
4. В момент времени 0 вычисление находится в исходной конфигурации стадии проверки при входе .
5. Не позднее, чем через шагов, переходит в состояние и, следовательно, принимает .
6. Для любого момента времени , конфигурация программы в момент времени получается из конфигурации в момент i одноразовым применением функции перехода .
Введем булевы переменные:
‑ в момент времени программа находится в состоянии , , где ‑ число различных состояний, причем , .
‑ в момент времени читающая/пишущая головка просматривает ячейку с номером , .
‑ в момент времени в -й ячейке записан символ , , где ‑ число различных символов в алфавите , причем .
4. Каждое из 6 сформулированных на этапе 3 условий может быть представлено в виде конъюнкции элементарных дизъюнкций введенных выше булевых переменных.
5. Анализ этих условий показывает, что для записи всех шести условий в общей сложности потребуется порядка элементарных дизъюнкций.
Длина каждой дизъюнкции не превосходит величины , где ‑ множество всех переменных, ограничено .
Индивидуальная задача, записанная с помощью цепочки символов ( ), может быть преобразована в индивидуальную задачу SAT. Отсюда вытекает утверждение теоремы, что задача выполнимости SAT есть -полная задача.
Дата добавления: 2016-06-05; просмотров: 2107;