20.Детерминированная и недетерминированная машина Тьюринга.

В таблице определены правила по количеству ячеек. Внутри ячейки размещается операционная часть правила. Строка и столбец, определяющие ячейку, содержат условную часть правила. Условная часть просто сообщает, в какой ситуации следует применить правило. Но могут существовать машины, в которых допускается применять любое из нескольких возможных правил с одинаковой условной частью.

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

Замечательным фактом является следующий (доказанный выше). Для всякой недетерминированной распознающей машины Тьюринга можно построить эквивалентную ей детерминированную машину.

21.Класс p и np.

Класс NP (NP – Nondeterministic Polynomial) – это класс языков с процедурой проверки, реализуемой за полиномиальное время на недетерминированной машине Тьюринга (любой детерминированный алгоритм есть частный случай недетерминированного алгоритма).

Класс P (P – deterministic Polynomial) – это класс языков с процедурой проверки, реализуемой за полиномиальное время на детерминированной машине Тьюринга.

Определение. Задача является NP-трудной, если к ней полиномиально сводится какая-нибудь NP-полная задача, но сама она не принадлежит классу NP.

Примером NP-трудной задачи является задача построения минимальной КНФ (конъюнктивной нормальной формы).

22.Классы co-np, pspace, npspace.

Определение. Класс co-NP - это класс всех языков, дополнительных к языкам из NP.

Очевидным образом co-NP  NP. Обратное соотношение является открытой математической проблемой.

Имеются определения классов сложности задач по реализуемым затратам памяти.

Определение. Класс PSPACE – это класс задач распознавания типа ДА-НЕТ, требующих полиномиальных размеров памяти для решающих их детерминированных алгоритмов.

Определение. Класс NPSPACE – это класс задач распознавания типа ДА-НЕТ, требующих полиномиальных размеров памяти для решающих их недетерминированных машин Тьюринга.

Имеет место следующее важное соотношение:

PNPPSPACE=NPSPACE

Результат PSPACE=NPSPACE известен как теорема Савича. Эта теорема доказывается, исходя из того, что для каждой недетерминированной машины Тьюринга имеется эквивалентная ей детерминированная машина Тьюринга.

23.Задача выполнимость и теорема с.Кука о полноте задачи выполнимость.

В практическом плане важным языком является язык ВЫПОЛНИМОСТЬ. Язык ВЫПОЛНИМОСТЬ содержит множество слов, представляющих все выполнимые системы дизъюнктов. Примерами дизъюнктов являются следующие:

и т.д.

Набор логических значений для переменных называется интерпретацией. Интерпретация, при которой дизъюнкт равен 1, называется выполняющей интерпретацией.

Задача ВЫПОЛНИМОСТЬ заключается в следующем. Имеется множество дизъюнктов. Спрашивается, имеется ли для этого множества дизъюнктов хотя бы одна общая выполняющая интерпретация? Если ДА, то множество дизъюнктов называется выполнимым. Если НЕТ, то множество дизъюнктов называется невыполнимым. Эта задача имеет только кажущуюся простоту. На самом деле, проблема упирается в отыскание эффективного алгоритма ее решения. Проблема распознавания языка ВЫПОЛНИМОСТЬ связана с распознаванием выполнимости данной системы дизъюнктов. Если система дизъюнктов выполнима, то это легко проверить, используя значения переменных выполняющей интерпретации. Проверку можно реализовать на недетерминированной в общем случае машине Тьюринга. Проверка просто устанавливает, удовлетворяет ли найденное решение условиям задачи.

Задача ВЫПОЛНИМОСТЬ очевидно, относится к числу задач распознавания. По смыслу вопроса она дает ответ «ДА» или «НЕТ». Если I – некоторая выполняющая интерпретация, то легко проверить (т.е. реализовать эффективный алгоритм проверки), что I выполняет каждый дизъюнкт системы. Эту проверку вполне можно осуществить с помощью детерминированного полиномиального алгоритма.

С. Кук доказал знаменитую теорему о том, что задача Выполнимость является универсальной в классе задач распознавания (этот класс получил короткое название NP (от слов Nondeterministic Polynomial)). Выполнимость универсальна в NP. Теорема Кука — Левина (также просто теорема Кука) утверждает, что за­да­ча о вы­пол­ни­мо­сти булевой формулы в КНФ (SAT) яв­ля­ет­ся NP-пол­ной.

Доказательство этой теоремы, по­лу­чен­ное Стивеном Куком в его фун­да­мен­та­ль­ной ра­бо­те в 1971 го­ду, стало одним из пер­вых важ­ней­ших ре­зу­ль­та­тов те­ории NP-пол­ных за­дач. Независимо в то же время эта теорема была доказана советским математиком Леонидом Левиным^[1].

В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. С. Кук (S. Cook) определил класс NP задач распознавания свойств следующим образом. Задача принадлежит классу NP, если:

1. решением задачи является один из двух ответов: «да» или «нет» (задача распознавания свойств);

2. требуемый ответ может быть получен на недетерминированном вычислительном устройстве за полиномиальное время.

Этот класс, как позже показал Р. Карп (R. Karp) в свою очередь содержит в себе другой широкий класс задач, названный Карпом NP-полные задачи, или NPC, сводимые в пределах этого класса одна к другой.

После появления результатов Кука была доказана NP-полнота для множества других задач. При этом чаще всего для доказательства NP-полноты некоторой задачи приводится полиномиальное сведение задачи SAT к данной задаче, возможно в несколько шагов, то есть с использованием нескольких промежуточных задач.