Новая заявка на решение задачи P vs. NP

На днях Норберт Блюм опубликовал на архиве препринт с названием «A Solution of the P versus NP Problem». Таким образом Блюм претендует на решение одной из задач тысячелетия, за которую кроме почестей полагается 1 миллион долларов.


Проблему равенства классов P и NP можно неформально определить следующим образом:

Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти? Задачи первого типа относятся к классу P, второго — к классу NP. Проблема равенства этих классов является одной из важнейших проблем теории алгоритмов. (Wikipedia)

#теория_сложности #p_v_ np #математика #логика #алгоритмы
https://telegra.ph/Novaya-zayavka-na-reshenie-zadachi-P-vs-NP-08-18