Недерминированная машина Тьюринга (НТ). Взаимосвязь классов Р и 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.





Читайте также:
Экономика как подсистема общества: Может ли общество развиваться без экономики? Как побороть бедность и добиться...
История русского литературного языка: Русский литературный язык прошел сложный путь развития...
Гражданская лирика А. С. Пушкина: Пушкин начал писать стихи очень рано вскоре после...
Опасности нашей повседневной жизни: Опасность — возможность возникновения обстоятельств, при которых...

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


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

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


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

Обратная связь
0.012 с.