一个以挑战计算极限而闻名的数学问题——却经常出现在我们生活中
本文参加百家号 #科学了不起# 系列征文赛。
假设你是一个小偷，在博物馆展览会上抢劫珠宝和稀有宝石。你是新来的，所以你只带了一个背包。你的目标应该是带着最有价值的东西离开，而不让你的包超载，直到它断裂或变得太重拿不动。你如何在这些物品中做出选择来最大化你的战利品？你可以列出所有的工件和它们的重量来手工计算出答案。但是对象越多，这种计算对个人或计算机来说就越麻烦。
这个虚构的难题，即“背包问题”，属于一类以挑战计算极限而闻名的数学问题。背包问题不仅仅是一个思维实验。澳大利亚墨尔本大学教授卡斯滕穆拉维斯基表示：“我们在生活中面临许多问题，无论是商业、金融，包括物流、集装箱船装载、飞机装载——这些都是背包问题。”“从实用的角度来看，背包问题在日常生活中无处不在。”
研究人员曾经利用这个问题的复杂性来创建计算机安全系统，但现在这些系统可以被破解，因为这个问题已经得到了很好的研究。今天，随着有能力打破数字通信锁的技术即将出现，背包问题可能会激发出为这场革命的新方法。
All or Nothing
背包问题属于一类“NP”问题，即“不确定多项式时间”。这个名称是指这些问题如何迫使计算机经过许多步骤才能得到解决方案，而这些步骤的数量会根据输入的大小急剧增加——例如，在装入特定的背包时要选择的物品的库存。根据定义，NP问题也有易于验证的解决方案。
理论家们开始关注的问题是，在计算机上执行特定任务的效率如何，举个例子：如果有一份100万件博物馆文物的清单，上面有它们的重量和价值，还有一个载重25磅的背包，那么一台电脑就必须遍历每一种可能的组合，以生成最赚钱的那一个。给定一个不确定的时间量，计算机可以使用蛮力来优化像这样的大型情况，但是在时间尺度上这是不实际的。
“我们认为，你可以用处理器覆盖整个地球，一直运行到宇宙热死，但仍然无法解决这些问题的适当版本的相对小的情况，”加州伯克利西蒙斯研究所的微软研究员说。
一些NP问题，如背包的例子，有一个特殊的性质：在20世纪70年代初，斯蒂芬·库克和理查德·卡普证明了各种NP问题都可以转化为一个形式逻辑问题。因此，如果一个问题可以用算法有效地解决和验证，那么所有问题都可以。这个性质被称为“NP完全性”。
计算机科学和数学中最棘手的问题之一是，这些“NP”问题，包括背包问题，是否真的不同于“P”问题，即那些可以在所谓的多项式时间内解决的问题。如果P=NP，那么就有可能解决所有易于验证的问题。因此，如果这种不平等持续存在，一般的背包问题将始终很难解决。
保密
密码学研究人员喜欢计算机难以解决的问题，因为它们在加密数字信息方面很有用。类似于背包问题的安全代码在这方面并不有用，因为它们太容易被破解，但受这一问题启发，人们正在开发更复杂的方法，也许有一天会在战胜下一代计算机中发挥作用。
在早期的背包式加密方法中，一个人的私钥是一个数字列表，其中每个数字都大于前一个数字的和。涉及该人的交换将使用一个看起来随机但由第一个列表中的数字和应用的特定转换组成的公钥。例如，如果公钥是[2,3,4,5]，则发送的消息“1,0,0,1”将被编码为2+0+0+5 = 7(因为2*1=2,3*0=0,4*0=0,5*1=5)。密钥之间转换涉及的秘密数字允许原始消息被公开。
要实现这一点，计算机还必须确定是否可以将任何给定的数字写成私钥中数字子集的和，这就变成了一个简单的背包问题。这就好比在一个背包里装上一堆大小不一的东西——比如戒指、一幅画、一辆车和一所房子——然后在检查过戒指和画是否合适之后，你就知道其他东西都塞不进去了。密码学家拉尔夫·梅克尔和马丁·赫尔曼在1978年描述了这个想法，但其他人在20世纪80年代早期找到了破解它的方法。
在今天的互联网上，私人信息交换经常使用涉及大质数的密钥，虽然分解大的数字是困难的，但它不被认为属于与背包问题相同的“NP完全”类。然而，计算机科学家已经准备好迎接一个量子计算机可以快速解锁这些密钥的未来。
量子计算机依赖于量子力学原理，量子力学原理认为，一个粒子不是位于一个单一的位置，而是有可能在许多不同的地方，除非它被固定下来并被测量。当普通计算机用0和1来编码信息时，量子计算机中的每一个“量子位”都有与粒子属性相关的大量可能的状态。量子计算机在浏览互联网或在咖啡店里写剧本方面没有用处，但它们将在一些类型的数学问题上释放出前所未见的力量。不幸的是，这些数学问题构成了现代网络安全的基础。
“从某种意义上说，我们真的很不幸，”斯蒂芬-大卫德维茨说。“我们设法将互联网的安全建立在一些问题的硬度上，这些问题对传统计算机来说似乎很难，但对量子计算机来说却很容易。”
虽然量子计算还处于起步阶段，但一些研究人员表示，我们在这方面的准备工作已经落后了。2016年，美国国家标准与技术研究院(NIST)呼吁采用新的抗量子加密方法。正在开发的这种类型的算法称为基于网格的密码学。它不使用数字，而是使用存在于多个维度的键，并涉及到由空间中等间距点构成的晶格结构的形成。问题是这些点在哪里，一个给定的随机点离晶格坐标有多近。本质上，这是一个不止一个维度的背包问题。
目前还不清楚我们离改变游戏规则的量子计算还有多远。尽管如此，许多密码学研究人员还是看到了一个紧迫的威胁。黑客可以截获加密的私人通信，为量子计算机的出现节省时间。这意味着，我们需要抗量子密码学，这比我们预期的量子计算机充分发挥潜力要早得多。
除了密码学的研究，背包问题在现实生活中无处不在。例如，你可能听说过“旅行推销员”问题，它也是NP完全问题。这里的挑战是为销售人员在返回起点之前找到在给定城市之间旅行的最短路线。与此密切相关的是车辆路径问题，它考虑多辆车辆进行交付。
巴西巴西联邦大学的教授已经着手解决这个问题，试图为卫生保健部门找到新的方法。她与一家家庭护理服务机构合作，在那里，医生和护士会去病人家里看望他们，并帮助他们优化路线，因为可供运输的汽车数量有限。
我们周围到处都是背包问题
对于我们这些不是计算机科学家并在现实生活中面临这些问题的人来说，我们有多好呢？当我们遇到类似背包问题的情况时，我们也会非常挣扎。在一项小实验中，参与者被要求在电脑屏幕上往背包里填满带有规定价值和重量的物品，随着物品选项的增加，人们往往很难优化背包里的物品。研究人员称，这一发现可能与“选择过多”有关：当我们有太多选择时，即使是在杂货店买果酱这样的简单情况下，我们也会变得僵硬。
然而，在现实世界中，我们却得过且过。注意力也是一个背包问题。开车时，我们会面临大量可能的干扰，比如鸟、云、收音机和周围的建筑物。我们必须把最相关的刺激放在我们的精神背包里——一般来说，我们是这样做的。
问题仍然是：考虑到NP完全问题对计算机来说比其他类型的难题更困难，那么对人来说也更难吗？如果事实果真如此，这将表明，这类问题的难度是问题的一个特征——一种自然属性。