Проклятие размерности

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

Рассмотрим простой пример алгоритма, переводящего запись числа M из двоичной системы счисления в шестнадцатеричную. Этот алгоритм будет брать блоки по четыре бинарных символа и определять соответствующую им цифру в шестнадцатеричной системе. Очевидно, время работы такого алгоритма будет пропорционально количеству двоичных разрядов в исходном числе, т. е. пропорционально длине входных данных (количество разрядов в числе M можно оценить как formula_01

Рассмотрим теперь алгоритм, решающий другую задачу: установить, является ли заданное число M простым. Алгоритм непосредственной проверки простоты будет перебирать все числа от 2 до formula_02и смотреть, делится ли число M нацело на какое-либо из них. Длина входной строки здесь также будет formula_03, а вот время работы в худшем случае будет пропорционально formula_04 Обратите внимание на то, что число действий определяется в зависимости от длины входной строки N, а не от числа M. Длина строки (количество информации) является более универсальной характеристикой, поскольку она может быть посчитана, даже если входные данные имеют нечисловой характер.

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

Пусть мы запускаем оба алгоритма на компьютере, выполняющем миллиард операций в секунду. И пусть первый алгоритм сопровождается сложной графикой, требующей для отображения каждого числа 5 млн операций, а второй алгоритм проверяет делимость числа M на любое другое число за одну операцию. Если алгоритм работает меньше 1/10 с, то считаем, что он работает почти мгновенно. В таблице приведено, как будет меняться время работы каждого алгоритма при разных длинах входных данных. Для сравнения нижней строкой в таблице приведено время работы второго алгоритма на вычислительной системе с производительностью в тысячу раз больше.

formula_05

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

Все алгоритмы разделяют на классы сложности в зависимости от характера возрастания числа выполняемых ими операций при увеличении длины входных данных N. К классу P относят алгоритмы, время которых возрастает не быстрее, чем некоторый многочлен (polynomial) от N. Частный случай полиномиальной зависимости — это линейная зависимость, пример которой мы уже видели. Алгоритмы класса P считаются быстрыми в том смысле, что могут применяться на практике. Существуют разнообразные хорошо известные алгоритмы класса P, выполняющие сортировку массивов, поиск некоторой подстроки в строке, решающие системы линейных уравнений и т. д.

Второй рассмотренный нами алгоритм не относится к классу P: для любого наперед заданного многочлена найдется такое значение N, что величина formula_06 окажется больше значения этого многочлена при том же N. Алгоритмы со временем работы, возрастающим быстрее любого полинома, помещаются в класс NP. Можно подумать, что аббревиатура NP происходит от «not polynomial», но на самом деле она означает «nondeterministic polynomial». Дело в том, что эти алгоритмы исполняются за полиномиальное время на недетерминированных машинах Тьюринга. Эти (гипотетические) машины вскользь уже упоминались. Их сущность заключается в том, что на каждом шаге машина может переходить не в одно, а сразу в несколько состояний, находясь в них как бы одновременно.

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

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

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

Существуют задачи класса NP, для которых неизвестно алгоритмов класса Р. Такие задачи мы будем называть NP-полными (хотя, строго говоря, некоторые задачи относят к промежуточным классам сложности). Установлена сводимость многих NP-полных задач друг к другу. Если для какой-то из них будет найден быстрый алгоритм, то на его основе можно будет построить быстрые алгоритмы решения и всех остальных задач. До сих пор нет доказательства того, что классы P и NP различны, т. е. что NP-полные задачи не могут решаться полиномиальными алгоритмами. Эта проблема, поставленная независимо Л. Левиным и С. Куком в 1971 году, входит в список «Millenium Prize Problems», состоящий из семи математических проблем, за решение каждой из которых Математическим институтом Клэя назначена премия в 1 млн долл. Многие практики, работающие с конкретными NP-полными задачами, убеждены, что P- и NP-классы не совпадают. Многие математики, пытавшиеся решить эту проблему, уверены, что сама она является неразрешимой (что, однако, тоже пока не доказано). И лишь оптимисты уверены в эквивалентности этих классов.

Почему же этому вопросу уделяется такое внимание? Время решения NP-полной задачи возрастает экспоненциально с ростом размерности задачи, поэтому такую ситуацию называют комбинаторным взрывом, пример которого мы видели в приведенной выше таблице. Это название связано с тем, что число многих комбинаторных объектов, таких как битовые строки или сочетания элементов множества, растет экспоненциально с увеличением их длины. Здесь уместно вспомнить о легенде, согласно которой мудрец, придумавший шахматы, попросил у индусского царя в качестве награды положить ему на доску зерна пшеницы: на первую клетку одно, а на каждую последующую — в два раза больше, чем на предыдущую. По легенде царь поначалу был рассержен пожеланием столь малой награды, но сейчас легко подсчитать, что число зерен было бы почти formula_07, и если бы каждая последующая клетка заполнялась через секунду, то это выглядело бы как гигантский взрыв. Стоит отметить, что и в настоящее время на вопрос о том, какова будет толщина листа бумаги, если его сложить пополам 50 раз подряд, значительная часть людей отвечает, что толщина составит до нескольких метров (хотя, опять же, несложно ее оценить примерно как расстояние от Земли до Солнца). Также быстро растет и число требуемых операций для решения NP-полных задач.

Эти задачи, обычно сводящиеся к перебору часто встречающихся комбинаторных объектов, оказываются практически неразрешимыми при достаточно большом N, как бы быстродействие компьютеров ни возрастало и как бы ученые ни пытались придумать для них полиномиальные алгоритмы. При этом NP-полные задачи являются гораздо менее надуманными, чем алгоритмически неразрешимые проблемы. Исследователи образно охарактеризовали данную ситуацию как проклятие размерности.

Алгоритмы класса NP, как правило, не могут применяться на практике, если только объем исходных данных не является сильно ограниченным. В частности, на этом факте основаны многие методы криптографии. К примеру, пусть мы знаем два больших простых числа. Мы можем их перемножить и результат перемножения сделать открытым ключом, с помощью которого происходит шифрование, а сами простые числа сделать закрытым ключом, с помощью которого происходит дешифрование. Мы можем передать открытый ключ по незащищенному каналу связи, получить по этому же каналу зашифрованную информацию и дешифровать ее с использованием известного нам закрытого ключа. Хотя нет защищенной передачи информации, способ практически безопасен (при достаточной длине ключа), поскольку алгоритм шифрования относится к классу P, а для дешифрования потребуется алгоритм класса NP (конечно, здесь приводится лишь общая идея, а не описываются сами алгоритмы шифрования). Еще остается вопрос, откуда нам самим взять большие простые числа. Из-за сложности получения таких чисел и эффективности их использования для шифрования они составляют предмет охраняемой тайны.

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

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