4. 肾脏交换

正常人有两个健康的肾来将体内的代谢废物滤出体外。如果只剩一个肾，人还是可以过正常的生活。如果两个肾都不能用，就必须用透析来维持生命，这不仅需要耗费大量金钱和时间，而且时刻都有可能死亡。

有两个健康肾的人可以捐献出其中一个，挽救双肾衰竭的病人，前提是捐献者的肾和受捐者的身体相容。通过简单的抽血就可进行这种相容性测试。

假如Alice不幸双肾衰竭，她的丈夫Bob同意捐献自己的一个肾。如果Bob的肾和Alice的身体相容，那么可以通过手术将Bob的一个肾摘除并移植给Alice。

但Bob的肾有可能受到排斥。还有一线希望，就是所谓肾脏交换项目。

假如另一个人Charlie也需要肾，愿意为他捐肾的是他兄弟David，而David的肾也和Charlie不相容。然而，如果David的肾与Alice相容，并且Bob的肾和Charlie的肾相容，那么就可以安排让四人同时上手术台，这样术后每个人都有一个好肾，挽救两条生命。

假设我们有了关于上述这样潜在的肾脏捐献者-接受者的数据库，就可通过有效的算法，让尽可能多的两对捐献者-接受者成功配对，达成肾脏交换。基本上这就是前一章介绍过的配对问题，很容易解决。

不止是两个人，还可以有更多人来配对。2011年年末，60场手术为30位患者移植了健康的肾脏，这是通过其他任何方法都不可能做到的。

然而如果允许多于两对的捐献者-接受者互换肾脏，如何找到尽可能多的多人搭配方案在目前还是一个NP完全问题。P=NP的证明在这里是性命攸关的，可比如何玩好扫雷重要得多。