21.Класс p и np

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

Итак, класс NP нами определен. В этом классе есть хорошие и плохие задачи. Подкласс хроших задач в NP называется классом P (polynomial). Подкласс плохих - вссе остальные. Гипотеза мирового значения, которая все еще не доказана, записывается как P=NP (?).

ОПРЕДЕЛЕНИЕ. Класс задач распознавания типа ДА-НЕТ с хорошим алгоритмом проверки решения называется классом NP (nondeterministic polynomial).

Нам надо объяснить, почему здесь фигурирует слова nondeterministic polynomial (недетерминированный полиномиальный). Речь идет о том, что все такие задачи можно решить за полиномиальное время на н е д е т е р м и н и р о в а н н о й машине Тьюринга. В самом деле, рассмотрим нашу задачу об угадывании слова. Пусть в общем случае слово состоит из N>2 букв. Тогда имеется N правил для выбора позиции для первой буквы, N правил для выбора позиции второй буквы, N правил для выбора позиции третьей буквы и т.д., всего N² правил. Однако имеется одно единственное вычисление, использующее ровно N правил, дающее правильный ответ. Это, разумеется, полиномиальное по сложности вычисление.

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

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

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

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

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

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

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

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

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

PNPPSPACE=NPSPACE

Результат PSPACE=NPSPACE известен как теорема Савича.

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

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

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

Система дизъюнктов задачи Выполнимость называется также конъюнктивной нормальной формой. Среди всех конъюнктивных нормальных форм имеются формы с наименьшим числом дизъюнктов. Такие формы называются минимальными КНФ, эквивалентными данному множеству дизъюнктов.

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

С. Кук доказал знаменитую теорему о том, что задача Выполнимость является универсальной в классе задач распознавания (этот класс получил короткое название NP (от слов Nondeterministic Polynomial)).