Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

ходит в следующее состояние и всё начинается вновь, пока не придёт к ситуа­ ции останова. § 4. NP класс Наиболее простыми считаются полиномиальные задачи, т.е. задачи класса Р. Другим, возможно, более широким, «сложностным классом» является тшасс NP. Эта аббревиатура обозначает выражение «разрешимых на Недетер­ минированной машине Тьюринга за Нолиномиальное время». Класс NP стали впервые изучать Эдмонде, Кук и Кири. Оказалось, что многие известные задачи принадлежат к NP классу. В обычных машинах Тьюринга (их называют детерминированными, чтобы отличать от недетерминированных) новое состояние, в которое машина пере­ ходит на очередном шаге, полностью определяется текуш,им состоянием и тем символом, который обозревает головка на ленте. В недетерминированных машинах Тьюринга для каждого состояния может быть несколько следуюш,их состояний, в соответствии с функцией перехода. И в каждом следуюш,ем состоянии может запускаться новая копия данной маши­ ны Тьюринга. Недетерминированность лучше всего понять, рассматривая алгоритм, ко­ торый производит вычисления до тех пор, пока не доходит до места, в котором должен быть сделан выбор из нескольких альтернатив. Детерминированный ал­ горитм исследовал бы сначала одну альтернативу, а потом вернулся для рас­ смотрения следуюш,ей альтернативы. Недетерминированный алгоритм может исследовать все альтернативы одновременно, «копируя», в суш,ности, самого себя для каждой альтернативы. Все копии работают независимо. Если копия обнаруживает, что данный путь безрезультатный, то она прекраш,ает выпол­ няться. Если копия находит требуемое решение, она объявляет об этом, и все копии прекраш,ают работать. Определим NP класс как класс задач, которые можно решить недетерми­ нированными алгоритмами, работаюш,ими в течение полиномиального време­ ни. Чтобы доказать, что некоторая задача принадлежит классу NP, достаточно построить недетерминированный алгоритм (алгоритм недетерминированной машины Тьюринга), который решает эту задачу за полиномиальное время. Нусть имеем, например, задачу выяснения суш,ествования в ориентирован­ ном графе гамильтонового цикла, длина которого меньше или равна М. Рассмотрим следуюш,ий алгоритм. begin Vi< —1 { Нункт отправления} 225