Индийский математик, возможно, решил задачу тысячелетия

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

Индийский математик Винэй Деолаликар, работающий в исследовательской группе Hewlett Packard в Калифорнии, объявил о решении одной из ключевых математических задач современности. Он доказал, что если ответ на какой-либо вопрос можно быстро проверить, то это еще не значит, что этот ответ всегда можно также быстро найти.

Если доказательство Деолаликара верно, то классы сложности алгоритмов P и NP не равны. P -- это множество алгоритмов, время работы которых пропорционально зависит от размера входных данных. Если решение при наличии дополнительных сведений можно быстро проверить, то задача относится к классу NP.

Один из классических примеров -- задача коммивояжера. Это одна из задач NP, принадлежность которой к P оставалась недоказанной. Нужно отыскать самый короткий маршрут, проходящий через несколько городов. Ответ на такой вопрос можно быстро проверить, но нет никакой вычислительной программы, которая способна эффективно найти его.

Деолаликар использовал методы статистической физики, чтобы показать, что нет принципиальной возможности быстро находить ответы на задачи NP. Математик пришел к выводу, что P ≠ NP -- так он и назвал доказательство, представленное (*.pdf) на рассмотрение коллегам.

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

За доказательство равенства или неравенства сложности P и NP Математический институт им. Клэя обещает выплатить Премию тысячелетия в размере $1 млн -- аналогично тому, какую сумму присудили Григорию Перельману за доказательство гипотезы Пуанкаре.

Многие ознакомившиеся с доказательством Деолаликара математики предварительно согласились с ним, сообщает New Scientist. Большинство из них и раньше склонялись к мнению, что P ≠ NP. Но окончательное мнение математическое сообщество составит не раньше опубликования окончательного варианта статьи, которое ожидается в течение недели.