Недетерминированные и детерминированные алгоритмы

Недетерминированные (вводится для того, чтобы классифицировать более подробно задачи не попадающие ни в Р(«хорошая» задача для которой существует полиномиальный алгоритм) ни в Е(задачи экспоненциальные по своей природе)) В общем случае определяет состояние алгоритма, как комбинацию адреса, выполняемой в текущей момент команды и значения всех переменных в данный момент. Алгоритмы называются детерминированными, если для любого их данного состояния существует не более 1-го следующего вполне определенного состояния. Иначе говоря, недетерминированный алгоритм, в любой момент времени может делать больше вещи.

Недетерминированные (Нд) алгоритмы не являются вероятными или случайными, они являются алгоритмами, которые могут одновременно находится во многих состояниях. Нд лучше всего понять, если рассматривать алгоритм который производит вычисление до тех пор, пока не доходит до места, в котором должен быть сделан выбор из нескольких альтернатив.

Детерминированный алгоритм исследовал бы одну альтернативу, затем возвращался бы для исследования другой альтернативы и т.д.

Нд алгоритм:

Может исследовать все альтернативы одновременно копируя себя для каждой альтернативы. Все копии работают независимо друг от друга. Эти копии могут создавать следующие копии, для дальнейшего исследования алгоритмов. Если какая-то копия обнаруживает что она сделана неправильный или безрезультатный выбор она прекращает работу, если находит решение, она сообщает всем копиям о своем успехе и все копии прекращают работу.

Очевидно, что никакое физическое устройство не способно на неограниченную Нд работу.

Детерминированный алгоритм (Дд)

Дд. алгоритмы являются абстракцией, которая позволяет игнорировать некоторые проблемы решения задач поиска с возвращением

Определяем класс NP как класс всех задач, которые можно решить Дд алгоритмами за полиномиальное время. Очевидно, что P NP т.к. путей может быть экспоненциально много, то алгоритмы, допустимые в этом случае намного сильнее, чем детерминированные алгоритмы, допустимые для задач класса Р.

NP-трудные и NP-полные задачи

Различные задачи, которые относятся и классу NP могут быть эквивалентными относительно некоторого отношения, которые определяем => обр.:

Опр. Задача Q полиномиально сводится к задаче R <=> выполн => условие

1. существует функция g(x) и f(x), вычисляемые за полиномиальное время

2. любого входа х частного случая задания Q значение g(x) является входом частного случая задания R

3. любые решения (выхода) у задания R значения f(y) является решением задачи Q

Т.о. для решения одной задачи (в данном случае Q) используется алгоритм решения другой задачи (в данном случае R)

Таким приемом часто пользуются при защите докторской диссертации

Опр. Если одновременно задача Q полиномиально сводится к задаче R и R полиномиально сводится к задаче Q, то Q и R полиномиально эквивалентны.

Опр. Задача называется NP – трудной (NP – сложной), если всякая задача из NP полиномиально сводится к данной.

Опр. Задача называется NP – полной, если она входит в NP и является NP – трудной