В начале XXI века, когда, пожалуй, всё человечество размышляло над футурологическими прогнозами, математики выбрали 7 проблем, которые должны определить развитие науки в ближайшие десятилетия, а то и столетие. Американский институт Клэя – один из крупнейших математических институтов мира обещал за решение каждой миллион долларов.
Одна из таких проблем, над которой размышляют лучшие умы человечества, выглядит так: P=NP?
Читается, «пи равно эн пи или не равно»? Речь вовсе не о числе пи, которое необходимо для вычисления площади круга.
Речь идёт об алгоритмах, их сложности и скорости вычислений. В наше время, это особенно важно, потому что приходится оперировать с очень большими объемами данных. А если алгоритм подведёт и не сможет совершать вычисления в реальном времени? Остановятся поезда, медицинские приборы, нефтепроводы и домны.
Мы уже говорили о скорости роста на примере графиков: линейный – поднимается вверх как прямая линия, полиномиальный (от слова полином, или многочлен) – побыстрее, ещё быстрее – экспоненциальный.
Здесь речь несколько о другом, о том, чтобы оценить скорость алгоритма.
Допустим у нас есть массив данных из N чисел. На то чтобы просто посчитать сумму всех чисел компьютеру требуется N единиц времени, и этот процесс не ускорить. Время работы алгоритма – линейное.
Усложним задачу: посчитать сумму всех пар элементов в массиве. Алгоритм будет состоять из двух циклов в каждом из которых потребуется перебрать N*N= N^2 элементов. Время работы такого алгоритма – квадратичное, то есть его можно выразить как много член второй степени от N.
В квадратичном случае при увеличении массива в 2 раза скорость работы вырастет в 4 раза, при увеличении в 10 раз – скорость вырастет в 100 раз, впрочем, могут быть и другие числа, если вместо N^2 окажется более сложное выражение в A N^2 +B N + C.
Перемножение матриц N на N (вспомните алгоритм с первого курса!) – алгоритм кубической сложности.
И так далее. Все алгоритмы, сложность вычислений которых можно определить с помощью многочлена степени К – пишется O (N^K) – образуют класс полиномиальных алгоритмов или P (то самое «пи»).
Бывает задача вычислить ответ, а бывает – проверить ответ.
Конечно, это нужно совсем не только преподавателям математики, проверяющим бесконечные «контрошки» и типовые расчёты.
Например, это необходимо для работы криптографических алгоритмов. А они сегодня встречаются повсюду: пользуемся ли мы банковской картой или системой обхода блокировок в интернете.
Так вот NP (читается «эн пи», near polynomial, почти полиномиальный) – класс задач, решение которых можно проверить за полиномиальное время.
Очевидно, что класс P входит в NP, какое время потрачено для вычислений, такое подойдёт и для проверки – «взял, да и подставил».
Мировой проблемой является обратный вопрос: если задача проверяется за полиномиальное время, можно ли и решать её за полиномиальное время? Конечно, у какого-то программиста руки кривые, и работать его программа будет дольше. Но если такой оптимальный алгоритм точно есть, значит стоит его искать!
То, что он есть, с позиций здравого смысла сомнительно. Но и контрпример, который опровергнул бы гипотезу P = NP построить не могут, хотя занимаются этим с начала 1970-х годов.
Про то, как шло обсуждение этой задачи, причем тут задача коммивояжера, если захотите, мы ещё расскажем. Или перейдём к другим великим задачам Миллениума.