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

Абстрактной моделью полиномиального алгоритма является так называемая детерминированная машина Тьюринга. Эта машина в каждый данный момент времени находится в строго определенном состоянии, за один шаг она совершает одно из некоторого конечного множества действий. Затем она переходит в следующее состояние и все начинается вновь, пока не придет к ситуации останова. § 4. NP- класс Наиболее простыми считаются полиномиальные задачи, т.е. задачи ютасса Р. Другим, возможно, более широким, «сложностным классом» является joiacc NP. Эта аббревиатура обозначает выражение «разре­ шимых на Недетерминированной машине Тьюринга за Полиномиаль­ ное время». Класс NP стали впервые изучать Эдмонде, Кук и Кири. Оказалось, что многие известные задачи принадлежат к NP- классу. В обычных машинах Тьюринга (их называют детерминирован­ ными, чтобы отличать от недетерминированнь!х) новое состояние, в которое машина переходит на очередном шаге, полностью опреде­ ляется текущим состоянием и тем символом, который обозревает го­ ловка на ленте. В недетерминированных машинах Тьюринга для каждого состояния может быть несколько следующих состояний, в соот­ ветствии с функцией перехода. И в каждом следующем состоянии может зап^'скаться новая копия данной машины Тьюринга. Недетерминированность лучше всего понять, рассматривая ал­ горитм, который производит вычисления до тех пор, пока не доходит до места, в котором должен быть сделан выбор из нескольких альтер­ натив. Детерминированный алгоритм исследовал бы сначала одну альтернативу, а потом вернулся для рассмотрения следующей альтер­ нативы. Недетерминированный алгоритм может исследовать все аль­ тернативы одновременно, «копируя», в сущности, самого себя для каждой альтернативы. Все копии работают независимо, Если копия 285