Математическая логика и теория алгоритмов

обнаруживает, что данный путь безрезультатный, то она прекращает выполняться. Если копия находит требуемое решение, она объявляет об этом, и все копии прекращают работать. Определим NF-класс как класс задач, которые можно реши недетерминированными алгоритмами, работающими в течение полиномиального времени. Чтобы доказать, что некоторая задача принадлелсит классу NP, достаточно построить недетерминированный алгоритм (алгоритм не­ детерминированной машины Тьюринга), который решает эту задачу за полиномиальное время. Пусть имеем, например, задачу выяснения существования в ориентированном графе гамильтонового цикла, длина которого меньше или равна М. Рассмотрим следующий алгоритм. while преемник (v „v) ^0 do begin v„„.| <- ВЫБОР(преемник (v „v)); nv<- nv+\; Длина пути <- Длина пути + длина дуги (v „v-i, v„v) begin Vi <- 1 S •^{2,3,.:.n} { Пункт отправления} {Множество вершин, которые нулсно посетить} {Общая длина пути} {Число пройденных вершин} {Пусть преемник (v „v.) обозначает допустимое, (не содержащее паразитных циклов) множество вершин, в которые можно попасть из v „v} Длина пути <- О т < - 1 end if nv=n and Длина пути < М then успех else неудача end 286