Алгоритмы для NP-трудных задач

Одним из центральных открытых вопросов компьютерных наук является вопрос о равенстве классов P и NP. Неформально его можно сформулировать так: «Верно ли, что для каждой алгоритмической задачи, решение которой можно быстро проверить, можно быстро найти решение?» Ответа мы до сих пор не знаем. NP-трудные задачи — в некотором смысле самые сложные из алгоритмических задач. Классический пример — задача 3-раскраски графа, в которой вершины данного неориентированного графа нужно покрасить так, чтобы концы всех рёбер были разного цвета. Действительно, проверить, является ли заданная раскраска правильной, легко. В то же время мы не знаем алгоритмов, которые бы за полиномиальное время проверяли, есть ли у данного графа такая раскраска. Таких задач очень много, они часто возникают на практике. Мы дадим обзор алгоритмов для таких задач. Более конкретно,

• узнаем, на основании чего некоторые задачи из класса NP считаются самыми трудными;
• узнаем формальную постановку вопроса о равенстве классов P и NP — вопроса, за решение которого положен приз в один миллион долларов;
• рассмотрим несколько техник решения NP-трудных задач на практике;
• воспользуемся SAT-солвером для того, чтобы очень быстро решить какую-нибудь комбинаторную задачу;
• увидим несколько примеров приближённых алгоритмов, которые быстро находят решение для трудной оптимизационной задачи, гарантированно не сильно отличающееся от оптимального;
• узнаем несколько красивых идей (как классических, так и совсем недавних), позволяющих избегать полного перебора в решении NP-трудных задач.

Отдельное внимание будет уделено открытым задачам данной области.

Курс предполагает знакомство слушателей лишь с базовыми алгоритмическими идеями (О-нотация, сортировки, базовые алгоритмы на графах, динамическое программирование). Проверить и освежить свои знания базовых алгоритмов можно в данном бесплатном онлайн-курсе.