x, y, z

NP-полные задачи

Николай Адрианов

Комментарии: 0
Часть 1

Часть 2

Часть 3

Часть 4

В этом курсе мы познакомимся с замечательной теорией NP-полных задач. Проблема (не)равенства классов P и NP — одна из «задач тысячелетия», за каждую из которых объявлен приз в миллион долларов. Мы разберемся в определении класса NP и научимся доказывать NP-полноту различных комбинаторных задач (классические теоремы Кука–Левина и Карпа). Особое внимание уделим задаче выполнимости булевых формул SAT. Мы поиграем с программами, решающими эту задачу, разберем какие алгоритмы они используют, как результатом их работы может быть доказательство, допускающее автоматическую проверку. Научимся сводить логические головоломки и математические задачи к SAT, поговорим о судоку, задачах теории Рамсея, недавнем продвижении в задаче о хроматическом числе плоскости и о «самом большом математическом доказательстве». Для других NP-задач мы обсудим несколько алгоритмов — как точных (переборных и на основе динамического программирования), так и приближенных. Довольно неожиданно разные NP-полные задачи (полиномиально эквивалентные с точки зрения точных алгоритмов) оказывается ведут себя совершенно по-разному с точки зрения приближенных.

Адрианов Николай Михайлович

Летняя школа «Современная математика» имени Виталия Арнольда
Московская область, г. Дубна, дом отдыха «Ратмино»
22-28 июля 2018 г.
Комментарии: 0