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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

x; мы опускаем очевидные детали.) С другой стороны, слова не из L алгоритм не
допускает (ни за какое время).
Новый алгоритм B моделирует работу алгоритма A и считает число шагов этого
алгоритма, сравнивая его с известной границей T. Если за время T алгоритм A допускает
слово x, алгоритм B также
допускает это слово и выдает 1. Если же A не допускает x за
указанное время, алгоритм B прекращает моделирование и отвергает слово (выдает 0).
Замедление работы за счёт моделирования и подсчета шагов не так уж велико и оставляет
время работы полиномиальным.
6.3 Проверка принадлежности языку и класс NP
Для определения сложностного класса NP нам потребуется ряд новых понятий, в
том числе рассмотрение задачи о гамильтоновом цикле.
Гамильтоновым циклом в неориентированном графе G = (V, E) называется
простой цикл, который проходит через все вершины графа. Графы, в которых есть
гамильтонов цикл, называются гамильтоновыми.
Задача о гамильтоновом цикле состоит в выяснении, имеет
ли данный граф G
гамильтонов цикл. Формально говоря,
HAM-CYCLE = {<G>: G – гамильтонов граф}.
Как решать такую задачу? Можно перебрать все перестановки вершин данного графа и
проверить, является ли хотя бы одна из них гамильтоновым циклом. Оценим время
работы такого алгоритма. Если мы используем представление графа с помощью матрицы
инцидентности, то
число вершин m в графе будет Ω( n ), где n = |<G>| – длина
представления графа G. Имеется m! различных перестановок вершин графа, и время
работы алгоритма равно Ω(m!) = Ω(
n !) = Ω(
2
n
), т.е. не является полиномиальным.
Таким образом, наивный алгоритм не дает эффективного решения задачи. (На самом деле,
есть основания предполагать, что полиномиального алгоритма для неё вообще не
существует.)
Пусть вы заключили пари с приятелем, который утверждает, что (нарисованный
перед вами на доске) граф является гамильтоновым. При этом вы не можете
быстро
проверить так это или нет. Тем не менее приятель может выиграть пари, если каким-то
образом отгадает гамильтонов цикл и предъявит его вам: проверка того, что данный цикл
является гамильтоновым, проста. Нужно лишь проверить, что предъявленный цикл
проходит через все вершины графа и что он действительно идет по рёбрам.
Проверяющий алгоритм
• Назовем проверяющим алгоритмом алгоритм A с двумя аргументами; первый
аргумент мы будем называть (как и раньше) входной строкой, а второй –
сертификатом. Мы говорим, что алгоритм A с двумя аргументами допускает вход x,
если существует сертификат y, для которого A(x, y) = 1.
• Языком, проверяемым алгоритмом A, мы назовем язык
L = {x ∈ {0, 1}
*
: ∃y∈{0, 1}
*
, для которого A(x, y) = 1}.
Другими словами, алгоритм A проверяет язык L, если для любой строки x∈L найдется
сертификат y, с помощью которого A может проверить принадлежность x к языку L, а для
x∉L такого сертификата нет. Например, в задаче HAM-CYCLE сертификатом была
последовательность вершин, образующая гамильтонов цикл.
Класс NP

Страницы