Профессор Южно-Уральского государственного университета Анатолий Панюков сообщает, что решил ещё одну из семи проблем тысячелетия. Одну из них - гипотезу Пуанкаре - ранее доказал Григорий Перельман. На этот раз речь идёт о равенстве классов задач P и NP.
В этой проблеме идёт речь о задачах, которые решаются с помощью компьютера. Задачи из класса P - задачи, имеющие "быстрое" решение (за степенное время - которое возрастает в зависимости от количества
данных в условии, как их размер в некоторой степени - квадрат, куб, и так далее). Задачи из класса NP - задачи, для которых возможно "быстро" проверить правильность решения. Сейчас такие задачи обычно решаются перебором возможных решений с теми или иными ограничениями, уменьшающими количество подлежащих проверке вариантов. Такое решение требует экспоненциального времени, которое возрастает как e в степени, зависящей от количества данных в условии, а это намного медленнее, чем
степенное время.
Пока решение опубликовано только в журнале "Автоматика и механика". Прежде чем его признает институт Клэя, вручающий премии за решение проблем тысячелетия, оно должно подвергнуться всесторонней проверке математиков всего мира. Если доказательство окажется верным, это будет значить, что такие задачи, как "Задача коммивояжера" (поиск кратчайшего пути в объезде нескольких городов) можно будет решить "быстро", и это даст толчок новым применениям компьютеров. С другой
стороны, вся криптография с открытым ключом строится на NP-задачах (разложение числа на множители, дискретное логарифмирование), и доказательство существования "быстрого" алгоритма их решения поставит криптографию под угрозу.
