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

x2, k), а решение v ∈{0, 1}, причём`v =1, если такой путь есть; v = 0 в против-
ном случае. Существует алгоритм поиска в ширину на графе, с помощью кото-
рого сформулированная задача решается за полиномиальное время.
       Рассмотрим теперь задачу о гамильтоновом цикле. Напомним, гамильто-
новым циклом в неориентированном графе называется простой цикл, который
проходит через все вершины графа. Задача о гамильтоновом цикле состоит в
ответе на вопрос, имеет ли данный граф гамильтонов цикл. Если в качестве ре-
шения организовать перебор перестановок вершин и проверку этих перестано-
вок на гамильтоновость, то, как и следует ожидать, время работы не будет по-
линомиальным; более точно, время работы такого алгоритма равно Ω (2 √ n), где
n – длина представления графа. ( Напомним, что число перестановок из m эле-
ментов равно m!. («эм – факториал»). Имеет место теорема: задача о гамильто-
новом цикле является NP – полной. К раскрытию понятия NP – полноты мы и
переходим в следующих пунктах.
       Проверяющим алгоритмом называется алгоритм А, имеющий два параме-
тра; первый – входная строка, второй – образец (или сертификат). Такой алго-
ритм считаем допускающим вход u, если существует образец v, для которого А
(и, v) = 1. Языком, проверяемым алгоритмом А, называется язык L =u ∈0,1 * 
( ∃ v ∈0,1 * А (u, v) = 1) .
       Итак, алгоритм А проверяет язык L, если для любого слова u∈СL найдет-
ся образец v, с помощью которого А может проверить принадлежность слова и
языку L, а для строки не принадлежащей языку такого образца нет. В задаче о
гамильтоновом цикле образцами могут быть последовательности вершин, обра-
зующие гамильтонов цикл. Гамильтоновость цикла в графе можно проверить за
полиномиальное время.

                                3.6.4 Класс NP

      Множество языков, для которых имеются работающие полиномиальное
время проверяющие алгоритмы ( с образцами, ограниченными по длине неко-
торыми многочленами) называется сложностным классом NP. Заметим, что
проверка языка в данном контексте несколько отличается от проверки языка
как таковой. А именно: для U∉ L могут существовать длинные образцы, кото-
рые в данном контексте отбрасываются (и потому остаются непроверенными в
прежнем смысле). Очевидно, всякую задачу из Р можно считать входящей в
NP: полиномиальный алгоритм, распознающий язык, в этом случае уже сущес-
твует, и для этого языка строится проверяющий алгоритм, не учитывающий
второй параметр. Итак, Р⊂ NP. Совпадают ли классы Р и NP?. Большинство
специалистов полагают, что в NP есть задачи, не решаемые за полиномиальное
время.
              3.6.5 Сводимость языков. NP – полнота языков
     Обычно мы полагаем, что одна задача сводится к другой, если (возможно)
преобразованные входы первой задачи являются входами другой. Говорят, что