Проблема P≠NP решена?

Сегодня обнаружил в открытом доступе новую попытку решения одной из важнейших задач теории алгоритмов — вопроса о равенстве классов сложности P и NP. Она, кстати, является одной из «проблем тысячелетия», за решение которых исследователь получает от Математического института Клэя 1 млн долл. Ещё одной такой проблемой была, например, гипотеза Пуанкаре, доказанная Григорием Перельманом.

Описание проблемы можно прочесть в Википедии (англ., рус.), а скачать доказательство — по этой ссылке.

Исследование Виная Деолаликара (Vinay Deolalikar) из лаборатории HP в Пало Альто датировано 6 августа. Можно с уверенностью утверждать, что в ближайшие несколько недель научная общественность будет усиленно искать ошибки в доказательстве.

Но то, что спустя два дня их вроде как не найдено, — уже повод для оптимизма. Например, два года назад, когда Xian-Jin Li опубликовал свою версию доказательства ещё одной «проблемы тысячеления» — гипотезы Римана, — первое указание на ошибку появилось уже на следующий день.

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365