Математическая логика и теория алгоритмов. Стенюшкина В.А. - 71 стр.

дящий х∈0,1* в y∈0, 1. Если существуют две вычислимые за полиномиа-
льное время функции f12, f21, переводящие два представления множества U друг
в друга, то эти представления называются полиномиально связанными. Справе-
дливо следующее утверждение.
      Основная лемма Пусть имеется абстрактная задача разрешения с множес-
твом условий U. Тогда для любых двух полиномиально связанных представле-
ний множества U соответствующие строковые задачи, при условии их полино-
миальности, эквивалентны с точки зрения их принадлежности классу Р.
      В силу этой леммы можно, как правило, не различать абстрактную задачу
и ее строковое представление. Для задач разрешения используются формаль-
ные языки и грамматики.

                 3.6.2 Допускающие и распознающие языки

      Языком L над алфавитом А называется некоторое множество последова-
тельностей символов (слов) алфавита А (построенных по определенным прави-
лам)
      Пример –L = ∧, 0, 1, 0110, 11, 001, … A={0,1}.
      Символ ∧ означает пустое слово, символ Ф означает пустой язык. Язык,
состоящий из всех возможных слов над заданным алфавитом А обозначается
через А*. Таким образом L⊂ А* для любого языка L над алфавитом А.
      На примере языков L⊂0,1* введём ещё несколько понятий из теории
формальных языков. Говорят, что алгоритм A допускает слово x∈{0, 1}*, если
А (х) = 1; отвергает, - если А(х) = 0. Алгоритм называется допускающим язык
L, если алгоритм допускает все слова L и только их. Если алгоритм допускает
все слова из L и не допускает слова из СL, то говорят, что этот алгоритм распо-
знает язык . Язык L допускается  распознается за полиномиальное время если
каждое слово языка допускается  распознается за время не большее O(nк) (n –
длина слова х, к не зависит от х, соответствующим допускающим  распознаю-
щим языком. На основании введенных понятий можно определить класс Р сле-
дующим образом: Р = L⊂0, 1 * существует алгоритм А, распознающий язык
 за полиномиальное время  . Имеет место теорема: Р = L  L допускается за
полиномиальное время . Таким образом, в рассмотренной ситуации допуска-
ющие и распознающие за полиномиальное время языки эквивалентны.
                         3.6 3 Проверяющие алгоритмы

      Рассмотрим задачу разрешения, связанную с задачей поиска кратчайшего
пути в графе. Дан неориентированный граф G = (X, Y), X – множество вершин,
Y – множество ребер. Требуется для двух вершин графа построить кратчайший
путь между ними. Это задача о кратчайшем пути. Здесь условием u является
тройка (G, x1, x2),x1, x2 ∈X, а решением v – последовательность (x1, …,x2) вер-
шин графа, составляющих требуемый путь. Одна из задач разрешения: по двум
вершинам графа и числу k определить, существует ли в графе путь, связываю-
щий заданные вершины, длина которого ≤ k. Теперь условием u является (G, x1,