6.5　解决一个不同的问题

有时候不论多么高明的技巧，都对某个NP问题无能为力。那么，我们可以试着解决另一个不同的问题。

简是帕罗奥图市一家名为图灵之家（Chez Turing）的餐馆的主厨，她想研发一种新的番茄酱来搭配她的名菜——砂锅意面。图灵之家是一家引领风潮的新派饭店，它开创了计算派菜系。简不直接使用食物做试验，而是向计算机输入她想要的颜色、味道、气味和口感，然后计算机就会搜索各种食材的组合，精确调配出所需的口味，这样研发的新菜不仅好吃，并且降低了制作成本和所含的热量。这一次，简想要研发一种深红色的酱，辛辣等级为5，口感类似燕麦但更顺滑，能轻触味蕾5和11，并能对砂锅意面本身的味道产生其他各种微妙的影响，以达到完美的进食体验。

计算机没能找到符合她所有要求的食材组合方式。于是简打电话给计算机天才汤姆，他答应过来帮助简，顺带赚取一顿免费大餐。汤姆尝试了他知道的所有启发式方法，也用了他查到的几种新方法。他还到云端，租借了Amazon机器上的计算时间，试图用真正生猛的计算能力来攻破问题。而那也没有奏效。他接着去拜访湾区的所有朋友，并宣布为第一个找到制作酱料方法的人提供一个令人垂涎的图灵之家的预定餐位。一周后，所有人都表示放弃，因为这个问题实在太难解决了。

汤姆回去告诉简这个坏消息。这是他第一次没能找到简需要的食材和制作方式。汤姆问：“能不能试试用其他方式来做酱料，比如稍微改变一下味道？”简不肯让步，认为酱料必须要具备这种味道和口感，否则会破坏砂锅意面在口中的感觉。汤姆又问：“那砂锅意面本身呢？”

既然为这种特定的砂锅意面找到合适的酱汁是一个很难的计算问题，简和汤姆转而搜索新的能够完美契合的砂锅意面和酱汁。这个任务稍微容易计算一些，计算机在数小时内就输出了一份食物配方。通过改变要解决的问题，图灵之家又有了一道新的招牌菜。

在另一种情境中，改变要解决的问题则令计算机安全专家们头痛不已，他们开发出的最新加密技术能让交易变得更加安全，前提是坏蛋只用专家们预想到的方法来破译密码。但是坏蛋们往往不按套路出牌，却偶尔能歪打正着。

智能卡表面上和信用卡一样，但里面内嵌了一个小小的处理器，存储着一个密钥。智能卡可以用来识别身份，也能存少量的钱，这样你在商店购物或者泊车咪表处交费时，就不用和集约化的计算机进行连接和通信也能完成交易。即使有人能截取到智能卡的输出和输入数据流，也很难猜出密钥。

假如托马斯在酒店工作，趁安妮去游泳的时候拿了她的智能卡。托马斯有一个特殊的读卡器，用它能试着给智能卡发送一些数据，然后看看返回了些什么数据。如果P=NP，那么窃贼能根据这些输入/输出行为找到密钥。而我们更有可能生活在P≠NP的世界里，找到密钥是很困难的。智能卡数据交换协议是经过精心设计的，本章提到的蛮力搜索或启发式算法等技术对于找到密钥都收效甚微。如果找不到密钥，托马斯通常只能把卡还给安妮，或者当安妮发现卡片丢失，直接给银行打电话注销这张卡。

而托马斯不是一般的身份窃贼。他能以设计者意想不到的方式来“使用”智能卡。他把卡扔到微波炉里加热几秒。你可别在家尝试这个，微波炉的能量会让智能卡或任何其他电子设备接近报废。即使是很短时间的微波加热处理，也可能导致某些电路的短路，即使不是永久性地损伤智能卡，也会让它的输入/输出行为变得无法预料。

无法预料的行为正是托马斯想要的。如果智能卡正常工作，他也许不知道如何找到密钥。而一个略微受损的智能卡虽然仍可以对输入的数据做出响应，但是输入/输出的行为也和原来不一样了。

新的输入/输出行为仍与密钥有关，但是原来那种令密钥难以被找到的设计失效了。这时如果托马斯再使用启发式或蛮力搜索等方法来寻找密钥，就有可能奏效。

一旦托马斯找到密钥，他就能用它制作两个和安妮原先正常的卡片一模一样的智能卡。托马斯把其中之一还给安妮，另一个留给自己。托马斯如果足够小心的话，就可以从安妮的账户偷钱，而安妮和银行可能要等几周或几个月后才会发现问题。

托马斯找到密钥的方式是，把一个被故意设计成难以解决的NP问题转变为一个完全没被设计过的问题。新一代的智能卡已经拥有了对抗微波攻击的机制。但我们绝不能低估那些一心想找到秘密信息的家伙们的想象力。