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

[Organon]

Недетерминированная Машина Тьюринга
Рассматривая детерминированную машину Тьюринга, мы коснулись и недетерминированной тоже.
Еще раз приведу определение:

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

С тем, что означает "существует не более одного правила", мы разобрались в прошлый раз. А что же значит "в противном случае"?

Напомню принцип действия машины Тьюринга.
Вдоль бесконечной ленты движется каретка, которая называется устройством управления (УУ). Каретка умеет читать символы на ленте и записывать туда другие символы алфавита. УУ может находиться в одном из нескольких состояний, которые описаны заранее. Его (УУ) действие для каждой конкретной ячейки определяются двумя факторами: 1) символом, записанным в эту ячейку, и 2) текущим состоянием.
Так вот, если это самое действие определено однозначно, то такая машина будет детерминированной.
А если нет? Тогда, предположим, что УУ в некотором состоянии перешло в ячейку, в которой оказался некоторый символ. УУ сверяется со своими правилами перехода и видит, что когда оно в данном состоянии встретило данный символ, оно может совершить не четко определенную одну вещь, а сразу несколько разных. И ничто не возбраняет ему (УУ) совершить любую из этих вещей.
Проще говоря, машина оказывается на развилке нескольких дорог, и никто кроме нее не может решить, куда же ей податься. И никто не знает заранее, что же она выберет. Именно поэтому она и называется недетерминированной. Ее поведение становится неопределенным.

И здесь есть несколько интересных моментов, на которые я хотела бы обратить внимание.

1. Как такая машина Тьюринга выбирает, куда ей двинуться на каждой развилке? Ответ на этот вопрос: да никак! Случайным образом. Самое печальное, когда путей у нас много, а правильный из них только один. Но и это печальное не так печально. Сейчас мы с этим разберемся.

2. Про "много путей, из которых правильный только один", я сказала не зря! Для классов задач, решаемых такими машинами (а чуть позже окажется, что недетерминированная машина Тьюринга в частности как раз и решает класс NP) из всех путей по всем развилкам результативным часто оказывается только один.
Если представить это наглядно, то можно вообразить себе детерминированную машину Тьюринга (ДМТ) в виде единственной дорожки, представляющей собой «путь вычислений». Недетерминированная машина Тьюринга (НМТ) в таком случае представляет собой сад расходящихся тропок. Говорят, что она имеет «дерево вычислений». В общем случае у этой машины число путей, по которым может развиваться вычисление, растет экспоненциально.
Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает.
То есть другими словами, если хотя бы один из всех возможных путей приведет к решению задачи, то такая машина пригодна для ее решения. Если же ни один из путей нас не устраивает, то, соответственно, и вся машина нам не подходит.
Говорят еще, что "ДА" и "НЕТ" здесь несимметричны. Думаю, теперь понятно, почему: для "ДА" нам достаточно одного подходящего пути из любого (пусть и очень большого) числа неподходящих; для "НЕТ" нужно, чтобы все пути не подходили одновременно.

3. На вид недетерминированная машина Тьюринга (НМТ) гораздо мощнее, чем детерминированная (ДМТ). И гораздо сложнее. Однако, оказывается, что они эквивалентны! Любую НМТ можно представить в виде ДМТ! Легче лёгкого! Доходя до каждой развилки мы начинаем клонировать машины. То есть недетерминированная машина делится на копии, каждая из которых развивает свою веточку дерева. И так на каждой новой развилке.
Википедия сравнивает этот процесс в многозадачной операционной системой. И в чем-то она права. Разве что вряд ли в операционной системе количество задач растет по экспоненте.

Конечно же, представление НМТ с помощью ДМТ требует значительно больше времени. Насколько больше — неизвестно. И если бы было известно, то задача, которую я и взялась рассматривать: «P = (?) NP» была бы решена!

Класс NP
Вот определение из Википедии:
Класс алгоритмов, выполняемых за полиномиальное время на недетерминированных машинах Тьюринга, называется классом NP.
Но определение это неполно! Всё так, да не совсем так.
Формальное определение дам в следующий раз. А сейчас просто расскажу, что это такое за класс.

Представьте, что у нас есть недетерминированная машина Тьюринга. Все веточки дерева дают нам 0, то есть не ведут никуда, и только одна дает нам 1, то есть, правильный ответ, — за полиномиальное время. "Полиномиальное время", как мы помним, — это количество шагов, не большее Const*N^C, где N — длина входных данных.
Если мы начнем перебирать все цепочки подряд и ходить по всем веточкам, вытягивая их в один линейный и очень длинный путь, мы увязнем, и всё это будет очень долго.
Но представьте, что у нас есть подсказка! На развилке она нам говорит, куда пойти, чтобы сразу добраться до результата!
Мы идем на полиномиальную веточку, которая ведет к ответу, и решаем задачу быстро!
Иногда эту подсказку, как правило, в виде готового решения, которое нужно только проверить, называют свидетелем. Иногда же рассматривают машину Тьюринга с оракулом. То есть, достигая развилки, машина Тьюринга обращается к оракулу — внешнему устройству, выдающему правильные ответы на некоторый круг вопросов.
На практике, однако, поиск свидетелей и построение оракулов — задача не из легких.

Вот, очень простой пример, который можно встретить в литературе в той или иной интерпретации.
Задача. Дано число: 15256677987889881453. Проверить, является оно простым или составным. (Честно скажу, я не проверяла, делится ли сумма цифр на три, не проверяла и другие, менее очевидные признаки делимости, но будем считать, что они не выполняются).
Если мы начнем действовать перебором и подбирать на роль кандидатов в делители все простые числа до квадратного корня из этого числа, мы потратим уйму времени!
Если же мы возьмем себе в помощь "свидетеля": число 123567898761 (которое я специально умножила на другое число, чтобы получить данное), то достаточно просто разделить одно на другое и убедиться, что мы поделили нацело. То есть, со свидетелем эта задача из разряда "нечего делать"; без свидетеля она становится весьма сложной.

Теперь отвлечемся от поиска делителей и/или доказательства простоты. Этот лишь пример, который весьма показателен, но сама задача проверки делится ли число на другое заданное число, конечно, же не относится к классу Р.
А вот если со свидетелем наша задача имеет алгоритмическую сложность Р, то стоит этого свидетеля лишиться, в общем виде получается задача класса NP. Эти задачи легко решить, зная, по какой веточке недетерминированной машины Тьюринга надо пойти, и трудно в противном случае.

На словах это выглядит не слишком убедительно, но давайте посмотрим на картинки.
Вот недетерминированная машина Тьюринга, вернее, конечно, не она сама — она выглядит совсем не так. Это дерево возможных решений. (Конечно, вовсе не обязательно, чтобы из каждого набора символ+состояние выходило три альтернативы. Ветвиться дерево может как угодно. Это просто для "быстроты рисования": исходя из удобства Ctrl+С Ctrl+V))). Я нарисовала только первые семь ходов, да и то опустила около половины веток. Представляете, что мы получим для реальной задачи?

Зато если у нас есть путеводная звезда в виде свидетеля или путеводная нить в виде оракула, то пройти по этому лабиринту нам не составит труда. Например, вот так:


Если красная веточка заканчивается за полиномиальное время, а все другие — не обязательно (они могут даже вообще никогда не заканчиваться), то перед нами графическая иллюстрация НМТ для задачи класса NP.