[287] NP-Complete

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美元,解决了漫画中的问题:

两种热翅,一种混合​​水果和一种采样板的组合

七个混合水果订单(这个解决方案不打算 – 见下面的琐事)

Leave a Reply

Your email address will not be published.

Categories