Задача на миллион долларов, которую программисты не могут решить уже 55 лет

Если завтра кто-то докажет, что P равно NP, рухнет почти вся современная криптография. Биткоин, банковские шифры, защищённые мессенджеры, пароли в базах данных. И за это доказательство Институт Клэя готов заплатить миллион долларов. Задача висит с 1971 года, и никто пока не сдвинулся с места.

О чём вообще спор

Выбрать из списка 100 городов маршрут, который проходит через каждый ровно один раз и влезает в бензобак, очень сложно. Перебор вариантов взорвёт любой суперкомпьютер. Но если вам дадут готовый маршрут, проверить его корректность можно за секунды. Проверить легко, найти с нуля почти невозможно. Именно этот разрыв и есть суть вопроса P versus NP.

Класс P включает задачи, которые компьютер решает быстро за полиномиальное время. Класс NP включает задачи, где быстро проверяется готовый ответ. Вопрос в лоб: это один и тот же класс или разные. Интуиция говорит, что разные, но никто пока это не доказал.

Почему это важно для индустрии

Современная криптография с открытым ключом держится на том, что разложить огромное число на простые множители долго, а перемножить их обратно быстро. Докажите P равно NP, и появится быстрый алгоритм взлома RSA. Банковские переводы, HTTPS, электронные подписи и блокчейны перестанут быть безопасными.

С другой стороны, полиномиальный алгоритм для задач NP дал бы революцию в логистике, биоинформатике, оптимизации расписаний, поиске лекарств и обучении нейросетей. Задачи, которые сейчас решаются эвристиками и приближёнными методами, начали бы решаться точно и быстро.

Кто должен знать про P versus NP

Любой разработчик, который хоть раз видел задачу о рюкзаке, задачу коммивояжёра или выполнимость булевой формулы, уже сталкивался с NP-полными задачами. Когда на собеседовании просят написать решение за полиномиальное время, а у вас на руках NP-полная формулировка, важно это распознать и честно сказать, что быстрого ответа нет. Это не слабость, а понимание границ вычислимости.

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

Источник:

https://t.me/data_analysis_ml/5196