Машина Тьюринга и проблемы остановки

     Сложность алгоритма определяется вычислительными  мощностями, необходимыми для его  выполнения. Вычислительная сложность  алгоритма часто измеряется двумя  параметрами: Т (временная сложность) и S (пространственная сложность, или требования к памяти). И Т, и S обычно представляются в виде функций от n, где n - это размер входных данных. (Существую и другие способы измерения сложности: количество случайных бит, ширина канала связи, объем данных и т.п.)

     Обычно  вычислительная сложность алгоритма  выражается с помощью нотации "О  большого", т. е описывается порядком величины вычислительной сложности. Это  просто член разложения функции сложности, быстрее всего растущий с ростом n, все члены низшего порядка игнорируются. Например, если временная сложность данного алгоритма равна 4n2+7n+12, то вычислительная сложность порядка n2, записываемая как О(n2).

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

     Эта нотация позволяет увидеть, как  объем входных данных влияет на требования к времени и объему памяти. Например, если Т= О(n), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т=О(2n), то добавление одного бита к входным данным удвоит время выполнения алгоритма.

     Обычно  алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит  от n: 0(1). Алгоритм является линейным, если его временная сложность О(n). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы - полиномиальны, их сложность - О(m), где m - константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем

     Алгоритмы, сложность которых равна О(tf(n)), где t - константа, большая, чем 1, a f(n) - некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна О(сf(n)), где где с - константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным.

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

     При условии, что единицей времени для  нашего компьютера является микросекунда, компьютер может выполнить постоянный алгоритм за микросекунду, линейный - за секунду, а квадратичный - за 11.6 дня. Выполнение кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция которого позволила бы ему противостоять следующему ледниковому периоду, в конце концов получил бы решение. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста мощи компьютеров, параллельной обработки или контактов с инопланетным суперразумом.

     Взглянем  на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность  такого вскрытия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если n - длина ключа, то сложность вскрытия грубой силой равна 0(2n). Сложность вскрытия грубой силой при 56-битовом ключе составляет 256, а при 112-битовом ключе - 2112. В первом случае вскрытие возможно, а во втором - нет.

     5. Сложность проблем 

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

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

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

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

     P<=NP<=EXPTIME

     Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно угадывая”, либо перебирая все предположения параллельно – и проверяет свое предположение за полиномиальное время.

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

     Если  все задачи класса NP решаются за полиномиальное время и на детерминированной  машине, то P=NP. Тем не менее, никем  не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что это классы неравны.

     Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что  и любая задача этого класса. Такие  задачи называются NP-полными. То есть, если такая задача решается за полиномиальное время, то P=NP.

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

     Наконец, существует класс задач EXPTIME. Эти  задачи решаются за экспоненциальное время. В настоящее время можно доказать, что EXPTIME-полные задачи невозможно решить за детерминированное полиномиальное время. Кроме того, доказано, что P<>EXPTIME.  
 

     6. Машина Тьюринга и алгоритмически неразрешимые проблемы 

     За  время своего существования человечество придумало множество алгоритмов для решения разнообразных практических и научных проблем. Зададимся  вопросом – а существуют ли какие-нибудь проблемы, для которых невозможно придумать алгоритмы их решения?

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

     Успехи  математики к концу XIX века привели  к формированию мнения, которое выразил Д. Гильберт – "в математике не может быть неразрешимых проблем", в связи с этим формулировка проблем Гильбертом на конгрессе 1900 года в Париже была руководством к действию, констатацией отсутствия решений в данный момент.

     Первой  фундаментальной теоретической  работой, связанной с доказательством  алгоритмической неразрешимости, была работа Курта Гёделя – его известная  теорема о неполноте символических  логик. Это была строго формулированная  математическая проблема, для которой не существует решающего ее алгоритма. Усилиями различных исследователей список алгоритмически неразрешимых проблем был значительно расширен. Сегодня принято при доказательстве алгоритмической неразрешимости некоторой задачи сводить ее к ставшей классической задаче – "задаче останова".

     Имеет место быть следующая теорема: не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного  алгоритма и его исходных данных (и алгоритм и данные заданы символами  на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.

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

     Тем не менее, можно попытаться сформулировать причины, ведущие к алгоритмической  неразрешимости, эти причины достаточно условны, так как все они сводимы  к проблеме останова, однако такой  подход позволяет более глубоко понять природу алгоритмической неразрешимости:

     а) Отсутствие общего метода решения задачи

     Проблема 1: Распределение девяток в записи числа;

     Определим функцию f(n) = i, где n – количество девяток  подряд в десятичной записи числа, а i – номер самой левой девятки из n девяток подряд: =3,141592… f(1) = 5.

     Задача  состоит в вычислении функции f(n) для произвольно заданного n.

     Поскольку число является иррациональным и  трансцендентным, то мы не знаем никакой  информации о распределении девяток (равно как и любых других цифр) в десятичной записи числа. Вычисление f(n) связано с вычислением последующих цифр в разложении, до тех пор, пока мы не обнаружим n девяток подряд, однако у нас нет общего метода вычисления f(n), поэтому для некоторых n вычисления могут продолжаться бесконечно – мы даже не знаем в принципе (по природе числа) существует ли решение для всех n.

     Проблема 2: Вычисление совершенных чисел;

     Совершенные числа – это числа, которые  равны сумме своих делителей, например: 28 = 1+2+4+7+14.

     Определим функцию S(n) = n-ое по счёту совершенное  число и поставим задачу вычисления S(n) по произвольно заданному n. Нет  общего метода вычисления совершенных  чисел, мы даже не знаем, множество совершенных  чисел конечно или счетно, поэтому  наш алгоритм должен перебирать все числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос о останове алгоритма. Если мы проверили М чисел при поиске n-ого совершенного числа – означает ли это, что его вообще не существует?

     Проблема 3: Десятая проблема Гильберта;

     Пусть задан многочлен n-ой степени с  целыми коэффициентами – P, существует ли алгоритм, который определяет, имеет  ли уравнение P=0 решение в целых  числах?

     Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий метод определения целых корней уравнения P=0 по его целочисленным коэффициентам.

     б) Информационная неопределенность задачи

     Проблема 4: Позиционирование машины Поста на последний помеченный ящик;

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

     Попытка построения алгоритма, решающего эту  задачу приводит к необходимости  ответа на вопрос – когда после  обнаружения конца кортежа мы сдвинулись вправо по пустым ящикам на М позиций и не обнаружили начало следующего кортежа – больше на ленте кортежей нет или они есть где-то правее? Информационная неопределенность задачи состоит в отсутствии информации либо о количестве кортежей на ленте, либо о максимальном расстоянии между кортежами – при наличии такой информации (при разрешении информационной неопределенности) задача становится алгоритмически разрешимой.