Помните ли какво е NP-пълният проблем? Как се различава от просто NP?

NP (недетерминирано полиномиално време) — това е клас задачи, за които решението може да бъде проверено за полиномиално време. Тоест, ако имате кандидат за отговор, можете бързо да проверите дали е правилен или не.

NP-пълните задачи са подмножество на NP, които са едновременно най-"трудните" в този клас. Ако някой намери полиномиален алгоритъм за решаване на всяка NP-пълна задача, тогава всички задачи от NP могат да бъдат решени за полиномиално време.

Основна разлика:

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

Пример: задачата за максимална клик в граф е NP-пълна, а задачата за проверка дали подмножество от елементи има сума равна на дадено число, е в NP.