Математическая логика и теория алгоритмов. Анкудинов Г.И - 86 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

5.2. Классы задач P и NP
Детерминированная машина M называется полиномиальной,
если существует полином p такой, что для всех n∈N, T
≤p(n).
M
Класс P-языков определяется следующим образом:
⎭
⎬
⎫
⎩
⎨
⎧
=
=
M
LL
M
LP
которой для
, машина ьнаяполиномиал существует
.
Задача распознавания Π при выбранном способе кодирования Κ
принадлежит классу P, если L(Π,Κ)∈P.
Недетерминированные вычисления
Рассмотрим недетерминированную машину Тьюринга (НДМТ)
M
, которая для любой формулировки z∈Z
у Π
задачи распознавания Π
выдает следующий результат:
если z∈Z
П.да
, то машина угадывает значение y,
удовлетворяющее R(z,y), и записывает код y на ленту рядом с z;
если z∉Z
, машина M сообщает об этом.
П.да у
Обратите внимание, что машина M
у
не читает ленту, а только
угадывает ответ и пишет его на ленту.
Детерминированная машина M
пр
по входу (z,y) проверяет
истинность R(z,y).
Рассмотрим НДМТ M в виде суперпозиции M
и M
у пр
. Эта
машина решает задачу Π за полиномиальное время, если найдется
такой полином p, что для любой задачи z∈Z
машина M
П.да у
найдет
такое значение y, что детерминированная машина M
пр
по значению
(z,y) проверит истинность R(z,y) за время p(l(z)). Это означает, что
размер y ограничен полиномом от l(z).
Класс NP - это все задачи распознавания, которые (при
разумном кодировании) могут быть решены недетерминированным
алгоритмом (N - non-deterministic) за полиномиальное время (P).
Для распознавания свойства R(z,y) можно сформировать пару
задач.
170

Страницы