Проблема равенства классов P и NP – первая в списке 7 задач тысячелетия. Это важнейшие открытые математические задачи, за решение которых институт Клэя даёт премию в миллион долларов. Проблема P=?NP не только первая, но и самая важная из них. Вкратце она звучит так: существует ли универсальный способ избавиться от полного перебора в алгоритмических задачах? Весь опыт человечества говорит, что нет, но строгого доказательства не известно и пока не предвидится: за почти полвека изучения проблемы мы лишь лучше поняли, почему она так сложна.
В лекции мы на простых примерах познакомимся с постановкой проблемы, изучим её историю, философские аспекты, связи с реальной жизнью и известные препятствия к её решению.
Рассказывает Даниил Мусатов
Лекция состоялась 28.01.2018
