Случайность и хаос - Рюэль Д.
Скачать (прямая ссылка):
TVP-полные (или трудные) задачи являются трудноразрешимыми. И еще более
потрясающим было бы то, если бы кто-то сумел доказать, что они являются
легкоразрешимыми...
Вы озадачены? Но все, что я в состоянии попытаться здесь сделать, -
просто дать краткие указания на эти темы, а также примеры задач, которые
считаются трудноразрешимыми.
Популярным примером является задача о странствующем торговце. Вам даются
расстояния между определенным количеством городов и разрешен определенный
полный пробег в милях. (Расстояния и полный пробег являются целыми
числами и рассчитываются в милях или какой-то другой единице.) Вопрос
состоит в том, имеется ли объездной путь, соединяющий все города,
максимальная длина которого не превышает полный разрешенный пробег. Это
вопрос, на который можно ответить либо "Да", либо "Нет". Если
предлагается определенный путь, то достаточно легко проверить,
удовлетворяет ли он условию полного разрешенного пробега. Однако
проверить по очереди все возможные пути, когда городов много, было бы
весьма трудно. Это пример TVP-полной задачи.
В общем, TVP-полные задачи требуют ответов "Да" или "Нет" и обладают
общей чертой: существование ответа "Да" можно проверить за полиномиальное
время. (Между ответами "Да" и "Нет" существует асимметрия, потому что
нельзя сказать, что ответ "Нет" можно проверить за полиномиальное время.)
Пусть "Задача X" будет вашей любимой задачей, на которую можно ответить
"Да" или "Нет". Допустим, что Задача X становится легкоразрешимой, если
вы имеете свободный доступ к решениям задачи о странствующем торговце, и
что задача о странствующем торговце становится легкоразрешимой, если вы
имеете свободный доступ к решениям Задачи X; тогда говорят, что Задача X
является TVP-полной. Несмотря на исчерпывающий поиск, не было найдено ни
одного полиномиального временного алгоритма для решения TVP-полных задач,
и все считают, что такового не существует. Однако этого никто не доказал.
Теперь удобно ввести NP-трудные задачи, которые трудны так же, как и TVP-
полные, но не требуют ответов "Да" или "Нет". Вот пример: задача спиновых
стекол. Входное сообщение является
134
Глава 22
Рис. 22.1. Каково максимальное значение Е(х)?
массивом чисел равных +1 или -1, где i и j идут от 1 до
некоторой величины п (например, от 1 до 100, в случае чего массив будет
состоять из 10 000 цифр ±1). Нужно найти максимальное значение выражения
п п
Е = ^Z^Za{hj)x(yi)x(yj)^ i=i j=i
где ж(1),... ,х(п) - допустимые величины +1 или -1. Таким образом, вам
необходимо сложить возведенные в степень п слагаемые, каждое из которых
равно +1 или -1, и сделать результат максимальным. Вероятно, вы не
верите, что это трудноразрешимая задача, и, быть может, она действительно
таковой не является, но никто так и не нашел эффективного алгоритма ее
решения. (Обратите внимание, что входное сообщение содержит биты,
возведенные в степень п, и последовательный поиск требует рассмотрения 2П
случаев.) Задача спиновых стекол является прототипом семейства задач,
которые возникают в физике неупорядоченных систем4. (Неупорядоченным
является "взаимодействие" a(i,j) между местами г и j.) Задача нахождения
максимального Е похожа на задачу нахождения высочайшего пика горной цепи
(см. рис. 22.1). В случае, изображенном на рисунке, это легко, потому что
х изменяется линейно (т. е. х является одномерным). В задаче спиновых
стекол геометрия пиков и долин является п-мерной... и трудно решаемой
(даже несмотря на то, что для каждого из п измерений возможны всего два
значения: +1 и -1).
Сложность, алгоритмическая
135
Создадим идеализацию - или, лучше сказать, метафору - задачи жизни.
Согласно этой метафоре задача жизни состоит в том, чтобы найти
генетическое сообщение х(1ж(п), которое дает очень большое значение
сложному выражению типа вышеприведенного Е. Согласно тому, что мы только
что сказали, это может быть очень сложной задачей. Однако существуют
некоторые признаки, указывающие на то, что вышеприведенная метафора
жизни, возможно, далеко не так ошибочна5.
Идея алгоритмической сложности также может послужить в качестве метафоры
сложности доказательства математических теорем или проектирования
космического корабля. Однако мы увидим, что доказательство теорем
приводит нас к еще более глубоким слоям сложности, нежели TVP-полные
задачи: более глубоким, более непонятным и более отвратительным.
Глава 23
СЛОЖНОСТЬ И ТЕОРЕМА ГЕДЕЛЯ
В 1931 году логик Курт Гедель, австриец по национальности, опубликовал
то, что, вероятно, являет собой единственный наиболее глубокий
концептуальный результат, полученный человечеством в двадцатом веке. Я
помню, что встречал Геделя в Принстонском Институте перспективных
исследований в шестидесятых-начале семидесятых. Это был невысокий
человек, изнуренный, с желтоватым лицом; кроме того, он носил в ушах
ватные пробки. Вот типичная история, которую я о нем слышал1. Приехавшему
коллеге позволили использовать рабочий кабинет Геделя, когда последний
