Новая заявка на решение задачи 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

В 1950-х годах советский математик Андрей Колмогоров выдвинул гипотезу о том, что сложность перемножения чисел всегда пропорциональна N². О том, как преодолевали этот порог сложности, и почему это важно для обычных людей рассказывает переводная статья от Дмитрия Иванова

#математика #алгоритмы
https://nplus1.ru/blog/2019/04/15/how-to-multiply-big-numbers