017. Малый ШАД - Алгоритмы для NP трудных задач - Александр Куликов

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

Видео 017. Малый ШАД - Алгоритмы для NP трудных задач - Александр Куликов канала Для школьников