Теория алгоритмов. Зюзысов В.М. - 66 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Например, задаче PATH соответствует язык PATH = {<G, u, v, k>: G = (V,E) –
неориентированный граф, u, v ∈ V, k ≥ 0 – целое число, и в графе G существует путь из u в
v, длина которого не превосходит k}.
Мы будем использовать одно и то же название – в данном случае PATH – для
обозначения задачи
и соответствующего языка.
Алгоритм допускает слово
Говорят, что алгоритм A допускает слово x∈{0, 1}
*
, если на входе x алгоритм выдает
результат 1 (A(x) = 1).
Алгоритм отвергает слово
Говорят, что алгоритм A отвергает слово x∈{0, 1}
*
, если на входе x алгоритм выдает
результат 0 (A(x) = 0).
Заметим, что алгоритм может не остановиться на входе x или дать ответ, отличный от 0 и
1. В этом случае он и не допускает и не отвергает слово x.
Алгоритм допускает язык
Говорят, что алгоритм A допускает язык L, если алгоритм допускает те и только те слова,
которые принадлежат языку L.
Алгоритм A, допускающий некоторый язык L, не обязан отвергать всякое слово x∉L.
Алгоритм распознает язык
Говорят, что алгоритм A распознает язык L, если A допускает все слова из L, а все
остальные слова отвергает.
Язык допускается за полиномиальное время
Язык L допускается за полиномиальное время, если имеется алгоритм A, который
допускает данный язык, причем всякое слово x∈L допускается алгоритмом за время O(n
k
),
где n – длина слова x, а k – некоторое не зависящее от x число.
Язык распознается за полиномиальное время
Язык L распознается за полиномиальное время, если имеется алгоритм A, который
распознает данный язык, причем время работы алгоритма на каждом слове длины n не
больше O(n
k
).
Теперь можно переформулировать определение сложностного класса P.
P = {L ⊂ {0, 1}
*
: существует алгоритм A, распознающий язык L за полиномиальное
время}.
На самом деле в данной ситуации нет разницы между языками, допускаемыми и
распознаваемыми за полиномиальное время.
Теорема 39. P = {L: L допускается за полиномиальное время}.
Доказательство. Если язык распознается некоторым алгоритмом, то он и
допускается тем же алгоритмом. Остается доказать, что если язык L допускается
полиномиальным алгоритмом A, то он распознается
некоторым (возможно, другим)
полиномиальным алгоритмом B. Пусть алгоритм A допускает язык L за время O(n
k
). Это
значит, что существует константа c, для которой A допускает любое слово длины n из L,
сделав не более T = cn
k
шагов. (Формально говоря, это верно для достаточно длинных слов

Страницы