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

Поделитесь материалом с коллегами и друзьями

Купить номер с этой статьей в PDF