Продолжение рассказа про алгоритмическую сложность, классы P, NP, и про NP-полноту II

[Organon]

Продолжаю рассказ про алгоритмическую сложность.
С О-нотацией мы разобрались, осталось разобраться еще с некоторыми вещами.
Итак, про то, что такое класс Р, нам уже известно.
Напомню: классом P (polynomial) называется множество алгоритмов, время работы которых не превосходит многочлена от размера данных. То есть сложность таких алгоритмов в терминах О-больших будет О(N^C), где N — размер входных данных.
Алгоритмы, принадлежащие классу P, считаются быстрыми. Оттого-то мы и испытываем к ним повышенный интерес.
К классу Р относятся алгоритмы сортировки, поиска в множестве, перемножения матриц, выяснения связности графов и некоторые другие.

(Я вот всё думала, почему вроде бы такие простые вещи как переход от Р к NP и NP-полноте всегда так запутанно написаны.... А теперь столкнулась с этим сама. Нужно предварительно рассказать о нескольких вещах, а одно знание цепляется за другое, и очень сложно выбрать то, с чего надо начинать. Я попробую начать с детерминированной машины Тьюринга).

Мы определили класс Р в терминах О-нотации. Но куда более полезно (а главное наглядно) будет определение сложности алгоритмов с помощью машины Тьюринга. А главное: на это очень пригодится в дальнейшем.

Что же такое Детерминированная Машина Тьюринга?
Определение я дам очень неформальное.
Представьте себе, что у нас есть бесконечная в обе стороны лента, разделенная на ячейки, в которых записаны какие-то символы — буквы из какого-то алфавита. Под алфавитом мы просто понимаем некоторый базисный набор знаков. Помимо символов алфавита, обязательно есть еще особый пустой символ, который заполняет все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Вдоль ленты движется каретка, которая называется управляющим устройством. Каретка может читать символы на ленте и записывать туда другие символы алфавита.
Каретка (управляющее устройство (УУ)) может находиться в одном из нескольких состояний, которые описаны заранее. Ее действие для каждой конкретной ячейки определяются символом, записанным в эту ячейку, и текущим состоянием.
Управляющее устройство работает согласно правилам перехода.
За каждый такт оно считывает текущий символ с ленты и в зависимости от своего состояния и значения прочитанного символа выполняет определенное правило перехода: 1) записывает в эту клетку новый символ, 2) переходит в новое состояние и 3) перемещается на одну клетку влево или вправо.
Не обязательно выполнение всех трех пунктов сразу. Содержимое ячейки или состояние УУ вполне могут остаться без изменения.
Описанный "аппарат" и есть Машина Тьюринга.
Машина Тьюринга обязательно должна иметь состояние, переход в которое будет означать конец работы, остановку алгоритма. Таких состояний может быть несколько. (*)

Есть такой знаменитый тезис Чёрча-Тьюринга, который говорит о том, что любой мыслимый алгоритм можно реализовать на машине Тьюринга.
На самом деле это очень важный результат. Представьте себе, что какой бы сложный алгоритм мы ни придумали, для абсолютно любого мы можем построить Машину Тьюринга.
"Мы можем" — это конечно для красного словца ))) На самом деле это не слишком просто. Но Чёрч и Тьюринг говорят, что теоретически это возможно.

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

Что это значит?
Детерминированность — одно из основных свойств алгоритмов. Говоря просто, это значит, что при выполнении каждого очередного шага, мы точно будем знать, какой шаг мы сделаем следующим. У нас нет распутья. Нам не надо кидать монетку, чтобы узнать, куда нужно пойти. Всё однозначно.
С недетерминированнной Машиной Тьюринга дело обстоит иначе. И она нам понадобится в очень скором времени.

Но сейчас речь идет только о детерминированной. И с ее помощью мы дадим еще одно определение класса Р.

Временем работы алгоритма T_M(x) при фиксированном входном слове x называется количество рабочих тактов машины Тьюринга от начала до остановки машины.
Пусть мы задаем на входе различные данные одинаковой длины. Каждый раз, в зависимости от начальных данных, количество тактов до остановки может разниться (сложность алгоритма так и вычисляется: в бесконечных сериях экспериментов).
Так вот, сложностью алгоритма, реализуемого такой машиной Тьюринга, максимальное время работы машины по всем входным словам фиксированной длины.

Если машина Тьюринга M, реализует некоторый алгоритм, и ее максимальное время работы не превосходит N^C для некоторого числа C и достаточно больших N, то говорят, что она принадлежит классу P, или полиномиальна по времени.

(*) Кстати, насчет терминальных символов, которые отвечают за остановку Машины Тьюринга. Еще одним свойством алгоритмов является результативность. Результативность как раз и означает, что любой алгоритм рано или поздно должен остановиться (и выдать результат, но это уже побочный продукт факта остановки). Если машина Тьюринга для какой-то задачи остановиться не может, значит, эта проблема алгоритмически неразрешима! И такие проблемы существуют!
(Но о них нужно писать отдельно, если у кого-то возникнет желание про них почитать))) На самом деле, это очень интересно!)