Случайность и хаос - Рюэль Д.
Скачать (прямая ссылка):
причем она устроена так, что останавливается, уже написав свое
собственное сообщение, которое и является ее ответом. Ответом может быть
"Да", или "Нет", или цифра, или какое-то более длинное сообщение. Можно
настроить машину Тьюринга так, чтобы она складывала или умножала целые
числа. Однако в действительности машина Тьюринга может делать гораздо
больше, нежели выполнять умножение: любая задача, которую способен
выполнить компьютер, также может быть выполнена и соответствующей машиной
Тьюринга. И кроме того, для различных заданий совсем необязательно иметь
бесконечное количество машин, потому что существует универсальная машина
Тьюринга. Чтобы реализовать на этой машине конкретный алгоритм, на его
ленте необходимо записать входное сообщение, содержащее описание
алгоритма и конкретные данные, которые необходимо обработать1.
Подведем итог. Алгоритм представляет собой нечто, что можно реализовать
на компьютере, причем мы можем воспользоваться даже очень примитивным
типом компьютера, который называется машиной Тьюринга. При наличии
конкретной задачи ее можно выполнить с помощью эффективных или
неэффективных алгоритмов, в зависимости от того, сколько циклов машины
Тьюринга потребуется для получения ответа. Тогда алгоритмическая
сложность задачи зависит от наличия эффективных алгоритмов ее решения.
Принятое определение эффективного алгоритма сравнивает длину L входного
сообщения (т. е. количество информации, которое в нем содержится) и время
Т (количество циклов универсальной машины Тьюринга), которое необходимо
для получения ответа. Если
Т < C(L + 1)п,
где Сип - некоторые постоянные, мы имеем полиномиальный временной
алгоритм. (Он называется так, потому что C(L + 1)п является полиномом по
L.)
Полиномиальный временной алгоритм считается эффективным, а задача,
которая ему соответствует, называется легкоразрешимой. Если п = 1, то
время, необходимое для выполнения алгоритма, по большей части,
пропорционально длине входного сообщения (плюс один); если п = 2, время
пропорционально квадрату длины входного сообщения (плюс один); и т.д.
Можно доказать, что определение легкости обработки не зависит от
конкретной
132
Глава 22
универсальной машины Тьюринга, которая используется. В качестве примера
рассмотрим задачу, в которой входное сообщение является целым числом и мы
желаем знать, делится ли это целое число на 2, на 3 или на 7. Вы не
удивитесь, что подобные задачи относятся к разряду легко обрабатываемых
(и вы, наверное, еще в школе изучили эффективные алгоритмы их решения).
По существу, современные компьютеры являются универсальными машинами
Тьюринга (они не отвечают требованиям классической машины Тьюринга только
в том, что не обладают бесконечной памятью). А потому специалистам по
вычислительной технике хотелось бы знать, какие задачи являются легко
разрешимыми. Однако нахождение эффективного алгоритма может оказаться
достаточно сложным. Так, например, произошло в случае с линейным
программированием, полиномиальный временной алгоритм для которого нашли
совсем недавно2. В линейном программировании, с технической точки зрения,
вопрос состоит в том, чтобы найти максимум линейной функции на выпуклом
многограннике. Теорема о минимаксе в теории игр приводит именно к такому
вопросу; да и, кроме этого, существует множество проблем распределения
ресурсов, которые также приводят к вопросам линейного программирования.
Следовательно, в данном случае, доказательство легкости решения может
иметь важные практические следствия.
Однако эффективные алгоритмы существуют не всегда. Допустим, что
единственный известный нам способ решения задачи заключается в
последовательном поиске среди всех сообщений длины L в двоичном алфавите.
На это уйдет время
Т > 2l.
В данном случае расчетное минимальное время, которое необходимо для
решения задачи, умножается на 2 всякий раз, когда длина L увеличивается
на 1. Мы наблюдали примеры подобного экспоненциального роста в первых
главах этой книги и убедились, что он быстро дает очень большие числа.
Таким образом, экспоненциальный временной алгоритм особенно практичным не
назовешь. В общем случае задача, для которой не существует
полиномиального временного алгоритма, считается трудноразрешимой.
Так каковы же примеры трудноразрешимых задач? И почему они таковыми
являются? Я предлагаю вам задать эти вопросы специалисту-теоретику,
который занимается вопросами вычислительной техники, если таковой
найдется среди ваших друзей. Отведите на ответ несколько часов и
попытайтесь на это время получить в свое распоряжение школьную доску.
Дело не в том,
Сложность, алгоритмическая
133
что все это слишком сложно, чтобы это можно было объяснить, а в том, что
это, скажем,... несколько специальная информация. Но, кроме того, все это
совершенно потрясающе. Ваш друг определит NP-полные задачи3, NP-трудные
задачи и объяснит вам, что такие задачи считаются трудноразрешимыми. Было
бы просто фантастически замечательно, если кто-то сумел бы доказать, что
