«За решение в общем виде получишь 50% к чаевым.»
Грубо говоря, к классу NP относятся те задачи, правильность решения которых можно проверить быстро (за полиномиальное время). К классу P относятся задачи, которые можно быстро решить.
Существует гипотеза P=NP (одна из центральных проблем теории алгоритмов, задача на миллион долларов). Гипотеза гласит, что если решение задачи можно быстро проверить, то саму задачу можно быстро решить. Гипотезу не могут ни опровергнуть, ни доказать уже более 30 лет.
Если хотя бы для одной NP-полной задачи будет найдено быстрое решение, то гипотеза будет доказана. Задача о ранце и задача коммивояжёра относятся к NP-полным.
Задача из стрипа является переформулировкой задачи о ранце.
