Недерминированная машина Тьюринга (НТ). Взаимосвязь классов Р и NP.





Определим класс NP в терминах недетерминированной машины Тьюринга.

Определение 1. Недетерминированная машина Тьюринга НТ – это машина Тьюринга с дополнительным угадывающим модулем (УМ) или оракулом, который способен записывать на ленту слова из внешнего алфавита А и разделяющий символ *. При этом алфавит внутренних состояний НТ содержит буквы qy, qn – соответствие ответам «да» и «нет».

НТ осуществляет работу в 2 этапа:

Стадия 1угадывание. На ленте машины записано слово a(I) в алфавите А, т.е. код задачи I, начиная с некоторой ячейки с номером 1 слева направо. Левее – в ячейке с номером 0 — записана разделяющая *.

 

a(I)

-2 -1 0 1

      , *   *          

c(I)

 

Угадывающий модуль, просматривая ячейку за ячейкой слово a(I), идет влево от разделительной ячейки и по одному символу за такт записывает слово c(I). Если угадывающий модуль останавливается, то происходит переход ко второй стадии работы НТ. При этом имеем конфигурацию: c(I)*q1a(I). (1)

Стадия 2 — решение. На этой стадии НТ работает, как обычная машина Тьюринга с начальной конфигурацией (1). Если машина через конечное число шагов придет в состояние qy, то говорят, что она принимает конфигурацию (1).

Определение 2. Говорят, что недетерминированная машина Тьюринга НТ принимает слово a(I), если существует слово c(I)такое, что конфигурация c(I)*q1a(I) принимается НТ.

Определим время работы НТ: , если a(I) принимается, где t1(I) — время работы на стадии 1, т.е. t1(I)=|c(I)|, t2(I) — время работы на стадии 2, т.е. t2(I)=tT(c(I)* a(I)), где T — соответствующая (обычная) машина Тьюринга.

Определим время работы НТ как функцию натурального аргумента

 

Определение 3. Говорят, что недетерминированная машина Тьюринга НТ решает массовую задачу П за полиномиальное время, если tHT(n)=O(p(n)) для некоторого полинома р. Другими словами, недетерминированная машина Тьюринга НТ решает массовую задачу П за полиномиальное время, если время её работы ограничено сверху полиномом от длины входа.

Определение 4. Класс задач NP – это множество задач, для которых существует недетерминированная машина Тьюринга НТ, принимающая за полиномиальное время те и только те слова, которые соответствуют индивидуальным задачам с ответом «да».

Очевидно, что PÍNP.

Теорема. Если задача П NP, то существует полином р(n) такой, что П может быть решена с помощью детерминированного алгоритма со сложностью О(2р(n)), где n – размер задачи П.

 

26. Ещё один подход к определению класса NP. Примеры недетерминированных алгоритмов. О проблеме P¹NP.

Определим NP как класс всех задач, которые можно решить недетерминированными алгоритмами, работающими в течение полиномиального времени, т.е. недетерминированными алгоритмами, в которых всегда есть путь успешного вычисления за время, полиномиальное относительно длины входной строки; очевидно P Í NP. Поскольку путей вычисления может быть экспоненциально много, вероятно, что алгоритмы, допустимые в этом случае, намного сильнее, чем детерминированные алгоритмы, допустимые для задач из P. Например, задача входит в NP, если она может быть решена недетерминированным алгоритмом поиска с возвращением (алгоритм 26.1), в котором

1) для всех k операций «вычислить Sk» и проверки «Верно ли, что Sk ¹ Æ?» и «Является ли (a1, a2, … , ak) решением?» можно сделать за полиномиальное время относительно длины входной строки,

2) длина каждого пути вычисления ограничена полиномом относительно длины входной строки.

k 0

вычислить Si

while Sk ¹ Æ do

[ не приводит к решению]

неудача

Алгоритм 26.1.Недетерминированный общий алгоритм поиска с возвращением для определения, имеет ли задача решение.

S {1, 2, … , n} a1 выбор (S) S S-{a1} k1 cost 0

while S ¹ Æ do

costcost +

if cost £ then успех

else неудача

Алгоритм 26.2. Полиномиально ограниченный недетерминированный алгоритм для определения, имеет ли задача коммивояжера с n городами ( представленная матрицей расстояний между городами n-го порядка)решение стоимости не больше b.

Очевидно, что имеет место включение P Í NP. Вопрос о строгости этого включения, то есть «верно ли, что P¹NP?» остаётся центральной нерешённой проблемой в теории сложности вычислений уже более 30 лет. Хотя общественное мнение склоняется к тому, что классы различны и полезность многих алгоритмов основывается на этой гипотезе, строгость включения до сих пор не доказана. Имеется некоторая (частичная) аналогия между качественной теорией алгоритмов и теорией сложности. Классы P и NP соответствуют классам разрешимых и перечислимых множеств и гипотеза о несовпадении классов P и NP есть аналог известной теоремы о существовании перечислимого неразрешимого множества.

Для того чтобы продемонстрировать силу полиномиально ограниченных недетерминированных алгоритмов и, следовательно, широту класса NP, мы покажем, что некоторый вариант задачи коммивояжера входит в NP. Если задана n´n матрица С расстояний между городами в задаче коммивояжера с n городами, то легко видеть, что алгоритм 22.1 можно модифицировать и получить полиномиально ограниченный недетерминированный алгоритм для определения, существует ли для любой границы b какой – либо маршрут стоимости не больше b; таким алгоритмом является алгоритм 26.2.

27. Примеры задач класса NP.

Входная строка l, на которой недетерминированный алгоритм дает ответ «да» за полиномиальное время называется догадкой или свидетелем.

1. Проблема выполнимости булевых формул. Напомним, что булевы формулы — это правильные выражения, построенные из булевых переменных р1, р2, … с помощью булевых связок Ù (конъюнкция), Ú (дизъюнкция), Ø (отрицание) и скобок. Проблема выполнимости булевых формул формулируется следующим образом: «По булевой формуле j(р1, р2, …, рn) выяснить, существует ли набор истинностных значений переменных а12, …, аn, для которого j(а12, …, аn)=1». Свидетельством ответа «да, выполнима» служит любой двоичный набор (а12, …, аn), на котором формула выполняется. Его размер n не превосходит длины формулы, то есть ограничен полиномом первой степени от её длины. Такие свидетельства имеются у всех выполнимых формул и только у них. Проверка того, что некоторый двоичный набор длины n свидетельствует о выполнимости формулы, сводится к вычислению её истинностного значения при заданных значениях переменных, что проверяется за полиномиальное время. Значит, данная задача принадлежит классу NP.





Читайте также:
Роль химии в жизни человека: Химия как компонент культуры наполняет содержанием ряд фундаментальных представлений о...
Гражданская лирика А. С. Пушкина: Пушкин начал писать стихи очень рано вскоре после...
Технические характеристики АП«ОМЕГА»: Дыхательным аппаратом со сжатым воздухом называется изоли­рующий резервуарный аппарат, в котором...
Решебник для электронной тетради по информатике 9 класс: С помощью этого документа вы сможете узнать, как...

Рекомендуемые страницы:



Вам нужно быстро и легко написать вашу работу? Тогда вам сюда...

Поиск по сайту

©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! Мы поможем в написании ваших работ!
Обратная связь
0.012 с.