11. Не могут они все быть легкими. Задача P/NP
В настоящее время математики используют компьютеры для решения самых разных задач, даже великих, и не считают это чем-то из ряда вон выходящим. Компьютеры хороши в числовых расчетах, но математика — это далеко не только «суммирование», так что ввести задачу в компьютер, как правило, очень непросто. Часто самое сложное — это преобразовать ее в такой вид, в каком ее можно решить путем компьютерных расчетов, и даже в этом случае компьютер иногда сопротивляется. Поэтому и в наше время решения многих великих задач находятся без или почти без участия компьютеров. Примерами тому — Великая теорема Ферма и гипотеза Пуанкаре.
В тех случаях, когда компьютеры использовались при решении великих задач (к примеру, теоремы о четырех красках или гипотезы Кеплера), они эффективно выступали в роли прислуги или помощников. Но иногда роли меняются, и математика становится служанкой компьютерной науки. Большая часть работы по первоначальному проектированию компьютеров шла в математическом ключе. Значительную роль в ней сыграла связь между булевой алгеброй — алгебраическим выражением формальной логики — и коммутационными схемами, разработанными, в частности, инженером Клодом Шенноном, создателем теории информации. Сегодня компьютеры и в практическом, и в теоретическом аспекте опираются на широкое использование многих самых разных областей математики.
Одна из задач тысячелетия по версии Института Клэя лежит в пограничной области между математикой и информатикой. В данном случае ситуацию можно рассматривать двояко: то ли информатика находится на службе у математики, то ли наоборот. На самом же деле требуется, да и развивается нечто другое, более сбалансированное, — партнерство. Задача касается компьютерных алгоритмов — математических скелетов, из которых вырастают компьютерные программы. Принципиальное значение здесь имеет концепция эффективности алгоритма: за сколько вычислительных шагов будет получен результат при определенном количестве входных данных. Практически эффективность говорит о том, сколько времени потребуется компьютеру на решение задачи заданного размера.
Слово «алгоритм» восходит к Средним векам, когда Мухаммад ибн-Муса аль-Хорезми написал один из первых трудов по алгебре. Еще раньше Диофант ввел в обращение элементы, которые мы сегодня прочно связываем с алгеброй: символы. У него они, однако, использовались как сокращения, а методы решения уравнений были представлены при помощи конкретных — хотя и типичных — примеров. Там, где мы сегодня написали бы что-нибудь вроде «x + a = y, следовательно, x = y — a», Диофант написал бы: «Положим x + 3 = 10, тогда x = 10 − 3 = 7» — и считал бы, что читатели должны сами сообразить, что эта идея будет работать и для любых других чисел вместо 3 и 10. Он готов был объяснить свой иллюстративный пример с применением символов, но никогда не стал бы оперировать символами как таковыми. Аль-Хорезми подробно разработал эту общую рекомендацию. Он сделал это при помощи слов, а не символов, но общая идея была верной, и именно он считается отцом алгебры. Более того, сам этот термин образован из названия его книги: она называлась «Краткая книга о вычислении посредством восполнения и противопоставления» («Аль-китаб аль-мухтасар фи хисаб аль-джебр ва-ль-мукабала»). Слово «аль-джебр», от которого и пошла алгебра, при этом означало «восполнение» и имело отношение к решению уравнений. А слово «алгоритм» произошло от средневековой латинизированной версии прозвища аль-Хорезми (т. е. «из Хорезма») — Алгорисмус — и означает в настоящее время специализированный математический процесс решения задачи, который при достаточно длительном ожидании гарантирует нахождение ответа на нее.
Традиционно в математике задача считалась решенной, если для нее в принципе можно было записать алгоритм, ведущий к ответу. Слово «алгоритм» использовалось редко: математики предпочитали представлять, скажем, формулу решения — частный случай алгоритма на языке символов. При этом было не слишком важно, может ли эта формула быть применена на практике: она сама по себе являлась решением. Но появление компьютеров изменило эту ситуацию. Формула, слишком сложная для ручных вычислений, вполне могла оказаться применимой, если привлечь на помощь компьютер. Зато ситуации, когда формула оказывалась слишком сложной даже для компьютера, стали вызывать раздражение, а такое тоже иногда случалось: конечно, любой алгоритм можно было попытаться просчитать на компьютере, но иногда расчет шел слишком медленно и не позволял получить ответ. Поэтому внимание ученых сместилось к поиску эффективных алгоритмов. И математики, и компьютерщики были кровно заинтересованы в получении алгоритмов, которые действительно позволяли бы за разумный промежуток времени получить ответ.
Если алгоритм имеется, относительно несложно оценить, сколько времени (измеряемого числом необходимых вычислительных операций) потребуется на решение задачи при определенном количестве входных данных. Это может требовать усилий и технических навыков, но зато вам известно, о каком именно процессе идет речь и, по крайней мере в общих чертах, что он делает. Гораздо сложнее разработать эффективный алгоритм, если тот, с которого вы начали, неэффективен. Еще сложнее решить, насколько плохим или хорошим может быть наилучший с точки зрения эффективности алгоритм для данной задачи, — ведь для этого нужно рассмотреть все возможные варианты, а вам неизвестно, что они собой представляют.
Первые работы по этому вопросу привели к грубому, но удобному разделению алгоритмов на эффективные (в простом, но неточном смысле) и неэффективные. Если продолжительность расчетов с увеличением количества входных данных растет относительно медленно, данный алгоритм эффективен, а задача проста. Если же продолжительность расчетов с увеличением количества входных данных растет очень быстро, то данный алгоритм неэффективен, а задача сложна. Опыт подсказывает, что, хотя встречаются задачи, которые в этом смысле можно назвать простыми, большинство задач к таковым не относятся и являются сложными. В самом деле, если бы все математические задачи были простыми, математики остались бы без работы. Соответствующая задача тысячелетия заключается в том, чтобы строго доказать, что существует по крайней мере одна сложная задача или что, вопреки нашему опыту, все задачи являются простыми. Эта задача известна как задача P/NP, и никто пока не представляет, как ее нужно решать.
В главе 2 мы уже сталкивались с приближенной оценкой эффективности. Алгоритм относится к классу P, если он имеет полиномиальное время работы. Иными словами, если число шагов, которые необходимо сделать для получения ответа, пропорционально количеству входных данных в какой-либо постоянной степени (скажем, в квадрате или кубе). Такие алгоритмы эффективны в самом широком смысле. Если входные данные представлены числом, то их количество — это не само число, а количество знаков в нем. Причина в том, что количество информации, необходимой для представления числа, соответствует месту, которое оно занимает в памяти компьютера, а это место пропорционально количеству цифр. Задача относится к классу P, если существует алгоритм класса P, который ее решает.
Любой другой алгоритм (или задача) принадлежит к классу не-P, и большинство таких алгоритмов неэффективны. Среди них есть алгоритмы, время работы которых экспоненциально по отношению к входным данным, т. е. примерно равно некоему фиксированному числу в степени, соответствующей размеру входных данных. Такие алгоритмы относятся к классу E и определенно неэффективны.
