Задача о равенстве классов вычислительной сложности P и NP

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

Задача о равенстве классов сложности

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

Институт Клэя доказательство Деолаликара, однако, пока не подтвердил, и математики, занимающиеся проблемой, нашли в решении ученого из HP ряд недочетов. Сейчас Деолаликар работает над новым, доработанным вариантом доказательства.

Пока без оценки
Отправить комментарий
КАПЧА
Вы человек? Подсказка: зарегистрируйтесь, чтобы этот вопрос больше никогда не возникал. Кстати, анонимные ссылки запрещены.
CAPTCHA на основе изображений
Enter the characters shown in the image.
Linux I класса
Linux II класса
Linux III класса
Счетчики
  • Самый популярный сайт о Linux и Windows 10
О Либератуме

Liberatum — это новости мира дистрибутивов Linux, обзоры, сборки, блоги, а также лучший сайт об Ubuntu*.