Title Text:General solutions get you a 50% tip.
Origin:https://xkcd.com/287/
https://www.explainxkcd.com/wiki/index.php/287:_NP-Complete
https://app-xkcd-cn.appspot.com/
“我的爱好”系列漫画中的另一个条目。 Cueball在餐馆订单中嵌入NP完全问题。具体来说，他不是通过明确说明名称，而是通过它们的总价格来订购开胃菜。这是背包问题的简化示例。这是组合优化中的一个问题，如下所示：如果你有一个可以容纳特定重量的背包（背包或帆布背包），并且你有一组物品，每个物品都有自己的指定值和重量，你必须选择放入背包的物品，使重量不超过背包的容量，并使所有物品的组合值最大化。
在计算复杂性理论中，NP代表“非确定多项式时间”，这意味着NP的问题需要多项式运行时间（即CPU运行程序所需的时间将是输入大小的多项式）来验证解，但是不知道是否可以在多项式时间内找到任何或所有解。多项式时间被认为是有效的;指数和更高的时间被认为是不可行的计算。 NP完全问题是，如果为它们中的任何一个找到多项式时间算法，则所有NP问题都具有多项式时间解。简而言之，可以很容易地检查NP完全问题的特定猜测，但系统地找到解决方案要困难得多。
服务员的问题是NP完全的，因为可以快速找到并检查给定订单的价格，但找到与价格匹配的订单要困难得多。这使得命令有效地成为服务器上的应用层拒绝服务攻击/算法复杂性攻击，类似于Slowloris或ReDoS。 （背包问题的NP完整性的正式证据可以在上面的链接中找到。）人类找到解决方案最直接的方法是首先列出选择一个开胃菜的所有（6）方法，有条不紊地开始，和他们的总成本，然后列出所有（21）选择两个开胃菜（允许重复）的方式，然后列出所有（56）选择三个开胃菜的方式，等等。由于八种开胃菜的任何组合都将超过15.05美元，因此该过程不必超出列出所有（1715）选择七种开胃菜的方式。
另一个着名的NP完全问题是Cueball最后提到的旅行商问题，指的是服务员声称他还有6张桌子可以到达。 （另见399：旅行推销员问题）。
标题文本指的是NP完全问题没有已知的多项式时间一般解，并且不知道是否可以找到这样的解。如果服务员能找到一个有效的通用解决方案，他将解决数学中最着名的问题之一。这个问题是克莱数学研究所在2000年提出的六个尚未解决的千年奖问题之一，其中一个正确的解决方案（包括证明不存在这样的解决方案）价值1,000,000美元。 50％的小费略低于公平。
对于那些好奇的人来说，正好有两种开胃菜组合，总计15.05美元，解决了漫画中的问题：
两种热翅，一种混合水果和一种采样板的组合
七个混合水果订单（这个解决方案不打算 – 见下面的琐事）
