Помните ли вы, что такое NP-полная задача? Чем она отличается от просто NP?

NP (nondeterministic polynomial time) — это класс задач, для которых решение можно проверить за полиномиальное время. То есть, если у вас есть кандидат на ответ, вы можете быстро проверить, правильный он или нет.

NP-полные задачи — это подмножество NP, которые являются одновременно самыми "трудными" в этом классе. Если бы кто-то нашёл полиномиальный алгоритм решения любой NP-полной задачи, то все задачи из NP можно было бы решать за полиномиальное время.

Главное отличие:

• NP — задачи, решения которых можно быстро проверить.
• NP-полные — задачи из NP, к которым можно свести любую другую NP-задачу (то есть они "наиболее сложные" в NP).

Пример: задача о клике максимального размера в графе — NP-полная, а задача проверки, является ли подмножество элементов суммы равной заданному числу — в NP.