NP-полнота
Надпись: Моё хобби: встраивать NP-полные задачи в ресторанные заказы.
[Ресторанное меню]
Меню: Ресторан Шоткис. Закуски. Фруктовый салат 86. Картошка фри 110. Овощная нарезка 134. Жареные крылья 142. Сырные палочки 168. Мясное ассорти 232. Сендвичи. Барбекью 262.
[Три человек за столом. Рядом официант]
Человек: Мы хотели бы что-нибудь из закусок ровно на 606 рублей.
Официант: … ровно Эм…
Человек: Вот некоторые статьи по задаче о ранце, которые могут помочь.
Официант: Вы знаете у меня ещё шесть других столов и
Человек: и как можно быстрее, конечно. Хотите что-нибудь по задаче коммивояжёра?
За решение в общем виде получишь 50% к чаевым.
Существует гипотеза P=NP (одна из центральных проблем теории алгоритмов, задача на миллион долларов). Гипотеза гласит, что если решение задачи можно быстро проверить, то саму задачу можно быстро решить. Гипотезу не могут ни опровергнуть, ни доказать уже более 30 лет.
Если хотя бы для одной NP-полной задачи будет найдено быстрое решение, то гипотеза будет доказана. Задача о ранце и задача коммивояжёра относятся к NP-полным.
Задача из стрипа является переформулировкой задачи о ранце.