Величайшие математические задачи

Традиционно в математике задача считалась решенной, если для нее в принципе можно было записать алгоритм, ведущий к ответу. Слово «алгоритм» использовалось редко: математики предпочитали представлять, скажем, формулу решения — частный случай алгоритма на языке символов. При этом было не слишком важно, может ли эта формула быть применена на практике: она сама по себе являлась решением. Но появление компьютеров изменило эту ситуацию. Формула, слишком сложная для ручных вычислений, вполне могла оказаться применимой, если привлечь на помощь компьютер. Зато ситуации, когда формула оказывалась слишком сложной даже для компьютера, стали вызывать раздражение, а такое тоже иногда случалось: конечно, любой алгоритм можно было попытаться просчитать на компьютере, но иногда расчет шел слишком медленно и не позволял получить ответ. Поэтому внимание ученых сместилось к поиску эффективных алгоритмов. И математики, и компьютерщики были кровно заинтересованы в получении алгоритмов, которые действительно позволяли бы за разумный промежуток времени получить ответ.

Если алгоритм имеется, относительно несложно оценить, сколько времени (измеряемого числом необходимых вычислительных операций) потребуется на решение задачи при определенном количестве входных данных. Это может требовать усилий и технических навыков, но зато вам известно, о каком именно процессе идет речь и, по крайней мере в общих чертах, что он делает. Гораздо сложнее разработать эффективный алгоритм, если тот, с которого вы начали, неэффективен. Еще сложнее решить, насколько плохим или хорошим может быть наилучший с точки зрения эффективности алгоритм для данной задачи, — ведь для этого нужно рассмотреть все возможные варианты, а вам неизвестно, что они собой представляют.

Первые работы по этому вопросу привели к грубому, но удобному разделению алгоритмов на эффективные (в простом, но неточном смысле) и неэффективные. Если продолжительность расчетов с увеличением количества входных данных растет относительно медленно, данный алгоритм эффективен, а задача проста. Если же продолжительность расчетов с увеличением количества входных данных растет очень быстро, то данный алгоритм неэффективен, а задача сложна. Опыт подсказывает, что, хотя встречаются задачи, которые в этом смысле можно назвать простыми, большинство задач к таковым не относятся и являются сложными. В самом деле, если бы все математические задачи были простыми, математики остались бы без работы. Соответствующая задача тысячелетия заключается в том, чтобы строго доказать, что существует по крайней мере одна сложная задача или что, вопреки нашему опыту, все задачи являются простыми. Эта задача известна как задача P/NP, и никто пока не представляет, как ее нужно решать.

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

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

Некоторые алгоритмы настолько эффективны, что выполняют работу намного быстрее, чем за полиномиальное время. К примеру, чтобы определить четность или нечетность числа, достаточно посмотреть на его последнюю цифру. Если (в десятичной записи) это цифра 0, 2, 4, 6 или 8, число — четное, в противном случае — нечетное. Весь алгоритм включает в себя не более шести шагов:

Последняя цифра — 0? Если да, то СТОП. Число четное.

Последняя цифра — 2? Если да, то СТОП. Число четное.

Последняя цифра — 4? Если да, то СТОП. Число четное.

Последняя цифра — 6? Если да, то СТОП. Число четное.

Последняя цифра — 8? Если да, то СТОП. Число четное.

СТОП. Число нечетное.

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