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

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