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

UptoLike

ВУЗ: 

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

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

Рубрика: 

• Прямая задача: верно ли, что для заданного z существует
такое y, что выполняется R(z,y)?
• Обратная задача: верно ли, что для заданного z не
существует такое y, что выполняется R(z,y)?
Если прямая задача принадлежит классу P, то и дополнительная
задача принадлежит классу P. Если же прямая задача принадлежит
классу NP, то не известно, принадлежит ли дополнительная задача
классу NP.
Недетерминированная машина M принимает x, если, по
крайней мере, одно вычисление для x является принимающим. Язык,
распознаваемый программой M:
*
L
={x∈Σ ⏐M принимает x}.
M
Время, за которое принимается x∈L
M
, – это минимальное число
шагов по всем вычислениям при входе x.
Временнáя сложность программы НДМТ M – это функция T
M
:
N→N (N − множество целых чисел):
() {}
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎝
⎛
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
=∈
∪=
равно машины
программой принятия время что
,, значение такоесуществует
1max
mM
x
nxLx
mnT
M
M
.
T
M
(n)=1, если нет ни одного входа длины m, принимаемого
программой M.
НДМТ имеет полиномиальную временную сложность, если
найдется такой полином p, что T
(n)≤p(n) для всех n≥1.
M
Формальное определение класса NP:
⎭
⎬
⎫
⎩
⎨
⎧
=
=
M
LL
M
LNP
что такая,работы, временем
ьнымполиномиал с НДМТ существует
.
Хотя недетерминированный алгоритм угадывает y, зависящий
некоторым образом от z, угадывающий модуль M
у
при этом
полностью игнорирует вход z.
Теорема 5.2. Если Π∈NP, то существует такой полином p,
что Π может быть решена детерминированным алгоритмом с
временной сложностью O(2
p(n)
).
171

Страницы