Главный научный сотрудник исследовательского подразделения Hewlett-Packard Винэй Деолаликар опубликовал решение задачи о равенстве классов вычислительной сложности P и NP — одной из семи «задач тысячелетия», за решение которых американский Математический институт Клэя назначил награду в 1 млн долл. До сих пор всего одна из них официально признана решенной — задача доказательства гипотезы Пуанкаре.
Задача о равенстве классов сложности P и NP заключается в попытке выяснить, справедливо ли высказывание о том, что если решение какой-либо задачи можно легко проверить подбором (за плоиномиальное время), то и ответ к ней можно подобрать достаточно быстро. Равенство означало бы, что многие сложные задачи можно решить быстрее, чем сейчас. Деолаликар доказывает, что классы сложности P и NP не равны, и так называемые NP-полные задачи, которые можно решить лишь за экспоненциальное время, существуют.
Институт Клэя доказательство Деолаликара, однако, пока не подтвердил, и математики, занимающиеся проблемой, нашли в решении ученого из HP ряд недочетов. Сейчас Деолаликар работает над новым, доработанным вариантом доказательства.
Отправить комментарий